[BOJ 1699] 제곱수의 합

이 문제는 이곳에서 확인할 수 있습니다.

이 문제는 한 숫자를 최소 몇 개의 제곱수의 합으로 나타낼 수 있는지 구하는 문제입니다.

DP(Dynamic Programming) 알고리즘으로 문제를 해결할 수 있습니다.
먼저 모든 숫자는 다른 두 숫자의 합으로 나타낼 수 있습니다. 4 = 1 + 3 or 2 + 4
위 예에서, 4의 최소개수는 1의 최소개수와 3의 최소개수를 합한 것과 같습니다.
따라서 모든 경우의 수를 검사해서 항의 개수가 최소가 되는 두 숫자 쌍을 찾으면 됩니다.