[Java] 백준 1699번 제곱수의 합

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

1699번: 제곱수의 합

이번 문제는 dp 문제입니다.

저는 점화식 짜는게 왜이렇게 힘든지 항상 dp문제만 만나면 머리가 많이 아프네요 ㅠㅠ

일단 저는 점화식을 짜기 위해서 노가다를 좀 했습니다.

 

1 = 1^2 			1
2 = 1^2 + 1^2			2
3 = 1^2 + 1^2 + 1^2		3

4 = 2^2				1
5 = 2^2 + 1^2			2
6 = 2^2 + 1^2 + 1^2		3
7 = 2^2 + 1^2 + 1^2 + 1^2	4

8 = 2^2 + 2^2			2

9 = 3^2				1
10 = 3^2 + 1^2			2
11 = 3^2 + 1^2 + 1^2		3
12 = 3^2 + 1^2 + 1^2 + 1^2	4

13 = 3^2 + 2^2			2
14 = 3^2 + 2^2 + 1^2		3
15 = 3^2 + 2^2 + 1^2 + 1^2	4

16 = 4^2			1
17 = 4^2 + 1^2			2
18 = 4^2 + 1^2 + 1^2		3
19 = 4^2 + 1^2 + 1^2 + 1^2	4

20 = 4^2 + 2^2			2
21 = 4^2 + 2^2 + 1^2		3
22 = 4^2 + 2^2 + 1^2 + 1^2	4
23 = 4^2 + 2^2 + 1^2 + 1^2 + 1^2 	5

 

이렇게 보면 규칙이 보이시나요?

저는 일정 제곱수가 반복되고 있다는 것을 찾았습니다.

 

5는 2^2 + 1^2 인데 1^2은 1에서 사용한 것과 같고

6은 2^2 + 1^2 + 1^2 인데 1^2 + 1^2은 2에서 사용한 것과 같죠

이렇다는 말은 5은 1 + dp[1], 6은 1 + dp[2]와 같습니다.

더 큰 숫자를 대입하면,

11은 3^2 + 1^2 + 1^2 이니 1 + dp[2]와 같습니다.

 

이러한 규칙 속에서 찾아낸것은 첫 제곱수 빼고는 이전 제곱수에서 가지고 온다는 것입니다.

그럼 구하고 싶은 숫자에서 첫 제곱수 값을 빼주고 + 1 만 해준다면 점화식이 완성됩니다.

dp[i] = Math.min(dp[i], dp[i - j*j] + 1) 이 점화식이 되겠네요.

 

package BJ;

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

public class BJ_제곱수의합 {
	static int N;
	static int[] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		dp = new int[N + 1];
		
		for (int i = 1; i <= N; i++) {
			dp[i] = i;
			for (int j = 1; j*j <= i; j++) {
				dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
			}
		}
		
		System.out.println(dp[N]);
	}

}

 

Ysik Github : https://github.com/Y1sik/Algorithm/blob/main/BJ/BJ_%EC%A0%9C%EA%B3%B1%EC%88%98%EC%9D%98%ED%95%A9.java