키큰개발자

문제 링크 : https://www.acmicpc.net/problem/1699

해결 방법 :

이 문제는 다이나믹 프로그래밍 문제다.

그렇기 때문에 먼저,

우리가 구하고자 하는 문제가 뭔지 본다. 

문제는 주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수 이다. 

ex) N = 3  , 1^2 + 1^2 + 1^2 = 3개 

    N = 7,  3^2 + 1^2 + 1^2 = 3개

나는 처음에 접근한 방법이 제곱을 했을때 (N 과 가장 가까운 수에 대해 최소항의 개수  + N- 가장가까운수 에대한 최소항의 개수) 로 점화식을 세워서 풀었었다. 하지만 이는 12를 구할때 깨져버린다. 

위점화식을 적용해보면, 9의 최소항의개수 + 12-9의 최소항의개수 = 4가 나오게 된다.

2^2 + 2^2 + 2^2 = 3개 이것이 최소개수인데 말이다. ㅜㅜ

다시 생각해 본 후 , 모든 경우를 고려하면 답을 구할수 있다고 봣다.

즉, 어떤 수 12는  제곱의 합에서 1의 제곱이 포함됬다고 보면 11의 최소항의개수 + 1 이 될것이다. 여기서 +1 은 1의 제곱이 포함됬기 때문이다.

12는 또 제곱의 합에서 2의제곱이 포함됬다고 보면 10의 최소항의 개수 + 1 이 된다.

12는 또 제곱의 합에서 3의 제곱이 포함됬다고 보면 9의 최소항의 개수 + 1이 된다.

이렇게 모든 경우를 포함하는 점화식을 세운다면 DP[N] = MIN ( DP[N], DP[N-j의제곱] + 1)  이될것이다.

(이때, j는 제곱해서 N보다 같거나 작을때까지의 수를 반복해서 도는 경우이다.)