백준 - 1699 : 제곱수의 합 (S2)

🏷️ python 🏷️ boj

수정일 : 2024-11-15


 1N = int(input())
 2
 3dp = [100000]*(N+1)
 4tmp = 1
 5
 6for i in range(1, N+1):
 7    if i**(1/2) % 1 == 0:
 8        dp[i] = 1
 9        tmp += 1
10    else:
11        for j in range(1, tmp):
12            dp[i] = min(dp[i], dp[i-(j**2)]+1)
13
14print (dp[N])