[코딩테스트] 제곱의 합(1699)

제곱의 합

DP

• 1의 제곱으로 만들어 낼수 있기 때문에, dp 인덱스에에 k로 초기화

import sys
input = sys.stdin.readline

n = int(input())
dp = [k for k in range(n+1)]

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