[JAVA] 백준 1699번

1699번 - 제곱수의 합

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int[] dp;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		dp = new int[N + 1];

		dp[1] = 1;

		for (int i = 2; i * i <= N; i++) { // dp값에 제곱수들인 경우 항의 최소개수 1저장
			dp[i * i] = 1;
		}

		for (int i = 2; i <= N; i++) {

			if (dp[i] == 0) {
				dp[i] = i;
			}

			for (int j = 1; j <= i / 2; j++) {
				dp[i] = Math.min(dp[i], dp[i - j] + dp[j]);
			}
		}

		bw.write(String.valueOf(dp[N]));
		bw.flush();
		bw.close();
	}

}

 

처음 문제에 접근한 방식

1. 주어진 N에 대하여 N에 최대한 가까운 제곱수를 구한 후 빼는 방식으로 최소 항의 개수를 구했지만 틀림

2. ex 89의 경우 ) 최대 제곱수를 뺴는방식인 경우 9*9 + 2*2 + 2*2 , 최소 항의 경우 8*8 + 5*5

 

정답을 맞춘 풀이방법

1. 제곱수들의 경우 최소 항의 개수 1을 dp배열에 저장함

2. dp[n] = dp[n-k] + dp[k]의 점화식을 반복문을 통해 최소값을 저장함

3. 정답을 맞추었지만 다른사람들의 문제해결 코드와 비교하면 시간이 약 10배정도 더 소모됨

4. 풀이를 보지않고 정답을 맞춘것에 의의를 두고 다른 효율적인 점화식을 확인해보아야함