[백준][DP] 1699. 제곱수의 합

1699. 제곱수의 합

 

• 내 풀이
  • i가 제곱수가 아니라면, 모든 가능한 제곱수 j²를 확인
    • i를 j²와 i-j²로 나눈다고 생각하고,
    • dp[i] = min(dp[i], dp[j²] + dp[i-j²])로 최소값을 갱신

n = int(input())
dp = [float('inf') for _ in range(n+1)]

dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
    if i**0.5 == int(i**0.5):
        dp[i] = 1
        continue
    for j in range(1, int(i**0.5)+1):
        dp[i] = min(dp[i], dp[j**2]+dp[i-(j**2)])

print(dp[n])