[백준] 1699번 제곱수의 합 (by Python)

문제

비슷한 문제인 1, 2, 3 더하기가 있지만 이 문제는 1, 2, 3이 아니라 n과 같거나 작은 모든 제곱수를 다 고려해야한다는 점에서 시간복잡도가 더 높은 문제이다. 그래서 Pypy3 환경에서만 성공할 수 있었다는 아쉬움이 있지만 이 문제에서 요구한 사고력은 내 풀이로도 충분하다고 생각해 더 이상의 최적화를 시도하진 않았다.

 

풀이

from math import sqrt

n = int(input())
sq_num = [i ** 2 for i in range(1, int(sqrt(n) + 1))]
dp = [1 if i in sq_num else i for i in range(n + 1)]
for i in range(2, n + 1):
    for j in range(1, int(sqrt(i)) + 1):
        dp[i] = min(dp[i], 1 + dp[i - j ** 2])
print(dp[n])