[백준] [1699] 제곱수의 합 (dp) (JAVA)

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

1699번: 제곱수의 합

---

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력 1 복사

7

예제 출력 1 복사

4

예제 입력 2 복사

1

예제 출력 2 복사

1

예제 입력 3 복사

4

예제 출력 3 복사

1

예제 입력 4 복사

11

예제 출력 4 복사

3

예제 입력 5 복사

13

예제 출력 5 복사

2

---

※ JAVA 코드 (제곱수의 합)

import java.io.*;

public class Main {

	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];
		
		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]);
	}
}

---

※ 생각정리 (제곱수의 합)

백준 제곱수의 합 문제는 현재 주어진 수 N에서 보다 작은 제곱수를 빼가며 최소 제곱수의 항개수를 구할 수 있다.

N이 9일때

dp[1] = 1

dp[2] = 2

dp[3] = 3

dp[4] = Math.min(4, dp[0] + 1) = 1

dp[5] = Math.min(5, dp[1] + 1) = 2

dp[6] = Math.min(6, dp[5] + 1) = 3

dp[7] = Math.min(7, dp[3] + 1) = 4

dp[8] = Math.min(8, dp[4] + 1) = 2

dp[9] = Math.min(9, dp[0] + 1) = 1

과 같은 패턴으로 값을 구할 수 있다.

즉, dp[N - (N보다 작은 제곱수)] + 1

 

-새벽코딩-