[Baekjoon]1699.제곱수의 합(DP)

Baekjoon

#1699. 제곱수의 합

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

---

수학적으로 좀 생각을 해봐야하는 문제였다. 어떤 자연수 n을 제곱수의 합으로만 나타낼 때 최소인 경우의 수를 구하는 문제이다. 예시는 문제에도 잘 나와있다. 

$$11=1^{2}+1^{2}+1^{2}+2^{2}+2^{2}$$

11은 이렇게 5개의 합으로 나타낼 수도 있지만 이것이 최소인 경우는 아니다. 

$$11=1^{2}+1^{2}+3^{2}$$

이처럼 3개의 제곱수의 합으로도 나타낼 수 있으므로 n이 11일때 답은 3 이다. 

여기서 한가지 착각을 하기 쉬운데 나도 똑같은 생각을 했다. 제곱수의 합으로 나타낼 때 n보다 작은 가장 큰 제곱수를 사용하여 나타낼 때가 최소일 거라고 생각한것이다. 하지만 그렇지 않았다. 예를 들어 43의 경우, 

$$43=6^{2}+2^{2}+1^{2}+1^{2}+1^{2}$$

이때 답은 5이지만

$$43=5^{2}+3^{2}+3^{2}$$

이때는 3이므로 n이 43 일때 답은 3이된다. 즉, n보다 작은 최대의 제곱수를 사용할 때가 최소가 되는 경우가 아니라는 말이다. 그렇기 때문에 모든 제곱수를 사용한 방법중에서 최소인 경우를 찾는 방식으로 찾아야한다. 먼저 배열 d를 정의하면

d[n] : n을 제곱수의 합으로 나타낼 수 있는 최소 개수 

43인 경우 모든 방법을 비교하는 것은 다음처럼 모든 경우를 알아볼 수 있다.

43-36=7이므로 7을 제곱수의 합으로 나타냈을때 최소의 개수에 1을 더하면 36을 사용하면서 최소 개수로 43을 나타낼 때 경우를 알 수 있다. 이는 즉 , d[7]+1 인데 1을 더하는 것은 d[7]방법에 36인 항을 하나 더해 43을 나타낸다는 의미이다. 이를  점화식으로 세우면

$$\mathbf{d[n]=min(d[n-j^{2}]+1, d[n])}$$

이 때 j는 j의 제곱수가 n보다 작을 때까지 수행한다. 핵심만 구현하면 다음과 같다.

for (int i = 1; i <= n; i++) {
    d[i] = i;
    for (int j = 1; j * j <= i; j++) {
	d[i] = Math.min(d[i - j * j] + 1, d[i]);
	}
    }

이런 문제는 여러가지 예시를 해보면서 발견적으로 추론하는게 상당히 중요한 포인트인 것 같다. 아직 갈 길이 먼 것같다...

<전체코드>