1699번 제곱수의 합(DP) - ☆

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

<전략>

1. n을 제곱수의 합으로 나타낼때, i가 포함된다고 하면, n = i^2 + ...  이렇게 나타낼 수 있다.

2. n - i^2을 제곱수의 합으로 나타낼때, j가 포함된다고 하면, n - i^2 = j^2 + ... 이렇게 나타낼 수 있다.

3. d[n] = min(d[n-i^2] + 1) 이다. +1은 i^2이 포함되기 때문.

Code