[백준] 1699 - 제곱수의 합 (Java)

[백준] 1699 - 제곱수의 합 (Java)

문제

https://www.acmicpc.net/problem/1699

풀이/후기

일단 필요한 제곱수를 미리 계산해서 num배열에 넣어주었다.

num = {1,4,9,...}

 

처음에 생각한 점화식(오답)

dp[i] = Math.min(i / num[j] + i % num[j], dp[i]);

점화식을 찾아낸 것에 뿌듯해하고 있었는데, 13에서 예외 상황이 발생했다.

내 점화식대로 하면

4 + 4 + 4 + 1

그러나 13은

9 + 4로 바로 표현될 수 있다.

제곱수끼리의 합으로 표현되는 경우인데

원래 점화식에서 이 부분만 수정을 해줄까 했으나

결국 점화식이 틀려서 발생된 상황이라 새로운 접근법을 생각해야 했다.

 

dp[i] = Math.min(dp[i - num[j]] + 1, dp[i]);

N에 가장 가까운 제곱수를 뺀 dp값 + 1

 

코드

package DynamicProgramming;

import java.io.*;

public class Problem1699 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int[] dp = new int[N + 1];
		int[] num = new int[N + 1];

		for (int i = 1; i < N + 1; i++) {
			num[i] = i * i;
		}

		dp[1] = 1;
		if (N > 1) {
			dp[2] = 2;
		}
		if (N > 2) {
			dp[3] = 3;
		}
		for (int i = 4; i < N + 1; i++) {
			//1의 제곱수로만 표현할 수 있는 개수 최소화
			dp[i] = i;
			for (int j = 1; num[j] <= i; j++) {
				//N에 가장 가까운 제곱수를 뺀 dp값 + 1
				dp[i] = Math.min(dp[i - num[j]] + 1, dp[i]);
			}
		}

		System.out.println(dp[N]);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/66e5158fa477dafd87d462be010047c05f744930

참고

https://vanillacreamdonut.tistory.com/120