제곱수의 합 풀이

문제 링크: https://www.acmicpc.net/problem/1699

백준 알고리즘 기초 1/2 400에서 13번째 - 1699번 제곱수의 합을 풀어보았다.

 

풀이: 코드는 https://lakelouise.tistory.com/61를 참고했고, dp는 계속 해도 어려운 거 같다.

 

C++

 

Python

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

Java