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])
백준 - 1699 : 제곱수의 합 (S2)
🏷️ python
🏷️ boj