[BOJ][DP] 1699. 제곱수의 합

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

처음에는 문제에 대한 접근을 

일단 될 수 있는대로 큰 제곱수 (x <= i)에 대한

경우의 수를 구하고 

dp[i - x]의 값을 더하면 될줄 알았다.

"어? 생각보다 금방 풀렸네?" 하며 기대에 부푼 마음으로 코드를 작성했으나..

채점 3%를 넘기지 못하고 오답이 떴다.

왜그런지 이유를 알 수 없어 한번 참고를 해보니 

무조건 큰 제곱수에 대한 경우의수만 구하는 것이 항상 최대는 아니라는 것이다.

즉.. 내가 이 문제를 그리디 알고리즘의 성격을 띈 방법으로 풀었다는 말.

예를 들어, 32의 최소항은 16 + 16 으로서 

1 + 1로 2가 되는 것. 

-----------------------------------

그러면 어떻게 풀어야 하냐.

일단 제곱수들의 최소항은 모두 1이다. 

ex) 4 = 2^2,   9 = 3^3,  16 = 4^4.....

저 최솟값들을 포함시키고 난 후, 

i값에서 최솟값을 뺀 수의 최소항수를 더하면 된다.

제곱수들은 한개만 있는 것이 아니므로,

그 중에서 제일 작은 값을 비교하여 구해내면 된다.

아래는 N = 19인 상황을 가정했다.

왜 dp값에 1을 더해 주냐면, 

dp[i - j * j]의 값에는

제곱수의 최소항수가 포함되있지 않다.

그래서 1을 더해주는 것. 

소스(Github)