[알고리즘/백준] 1699: 제곱수의 합(python)

자기 자신보다 작은 제곱수를 이용하여 푸는 문제이다.

1부터 시작하여 자기 자신에서 제곱수를 빼고 해당하는 dp에 +1 해주면 된다.

min(dp[i], dp[i - 제곱수] + 1)

N = int(input())
dp = [i for i in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, int(i ** 0.5) + 1):
        if dp[i] > dp[i - j * j] + 1:
            dp[i] = dp[i - j * j] + 1
print(dp[N])