글 읽기 - 문제 1699 질문

kisrin4319 7년 전 0

아직 dp로 코드 짜는 법을 제대로 알지 못해서 일단 brute force 식으로 짜본 코드입니다.

sqrt를 활용해 최대 제곱수에 가깝게 만든 후 숫자를 줄여나면서 최소항 갯수를 구하는 식으로 구현해봤습니다.

테스트 케이스랑 몇개는 되는것 같은데 오답 처리가 되어 이렇게 질문 드립니다.

public static void main(String[] args) throws IOException {

		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));

		long N = sc.nextLong();
		long num = (long) Math.sqrt(N);
		
		

		long min = 999999999;
		for (long i = num; i >= 1; i--) {
			long temp = N;
			long index = i;
			long count = 0;
			while (temp > 0) {
				if (temp - Math.pow(index, 2) == 0) {
					count++;
					break;
				} else if (temp - Math.pow(index, 2) > 0) {
					temp -= Math.pow(index, 2);
					count++;
				}
				if (temp < Math.pow(index, 2)) {
					index--;
				}
			}
			min = Math.min(min, count);
		}
		out.println(min);

		out.close();
	}

cozyyg 7년 전 0

때로는 최대 제곱수에 가깝게 만드는 것이 최선이 아닐 때가 있습니다.

12=9+1+1+1이 되지만 12=4+4+4로 하면 더 적은 개수로 할 수 있습니다.

32=25+4+1+1+1보다 32=16+16이 더 개수가 적습니다.

https://www.acmicpc.net/proble...

동전 교환 알고리즘(Coin Change)을 구글링해서 찾아보면 도움이 될 수도 있습니다.

kisrin4319 7년 전 0

위 제 코드를 실행 시켰을 시에 min = 2로 나오게 구현되어있습니다.

물론 12를 넣었을 경우에도 min=3 으로 출력이 되는데 최대 제곱수에 가깝게 만드는것 부터 잘못일까요?

cozyyg 7년 전 3

아 반례 찾기 어렵네요...

43=25+9+9에서 43에는 3이 나와야 합니다.

저 코드에서는 4가 나옵니다.

12나 32 같은 경우에는 첫 번째 수를 잘 잡으면 그 다음부터는 최대 제곱수를 잡아도 되지만, 43의 경우 저 코드에서는 25 다음에 16을 택하게 되어 최소인 25,9,9를 찾을 수 없습니다. brute force로 구현하기는 좀 어려운 문제일 듯 합니다.

kisrin4319 7년 전 0

도움 주셔서 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 1699 질문

kisrin4319 7년 전 0

cozyyg 7년 전 0

kisrin4319 7년 전 0

cozyyg 7년 전 3

kisrin4319 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말