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

생각보다 이해가 좀 어려웠다ㅜ

코드

n = int(input())
dp = [0] + [float('inf')]*n 
for i in range(1, n+1):
    j = 1
    while j*j <= i:
        dp[i] = min(dp[i], dp[i - j*j] + 1)
        j += 1
print(dp[n])

dp = [0] + [float('inf')]*n

• 무한대인 최대값으로 두고 min()을 하는게 좋음.

while j*j <= i

• 이는 'i'보다 작거나 같은 제곱수만 고려하도록 하기 위한 것.

dp[i] = min(dp[i], dp[i - j*j] + 1)

예를들면

• square = 1(1^2)의 경우 dp[26] = min(dp[26], 1 + dp[26 - 1])을 수행합니다.
• square = 4(2^2)의 경우 dp[26] = min(dp[26], 1 + dp[26 - 4])가 됩니다.
• square = 9(3^2)의 경우 dp[26] = min(dp[26], 1 + dp[26 - 9])을 수행합니다.

이렇게 자신보다 작은 값의 제곱수를 돌려보는것.