[BOJ_1699] 제곱수의 합

 

입력 받은 수를 제곱수의 합으로 나타낼 때 각 항(반드시 양의 정수의 제곱)의 수의 최소값을 구하는 문제입니다.

 

수	1	2	3	4	5	6	7	8	...
항의 개수	1	2	3	1	2	3	4	2	...

DP 테이블을 갱신시켜 나가는데

바깥 루프에서는 dp[i] = i 즉, 그 수 만큼의 값으로 채워주고 이것이 최댓값입니다.

안쪽 루프에서는 더 작은 횟수로 줄일 수 있을 때 갱신 해 나갑니다.

dp[i] = min(dp[i], dp[i-j**2] + 1)

이것이 가장 핵심이 되는 구문인데 이 식을 생각해 내는것이 정말 어려운 것 같습니다. 여기서 +1을 해주는 이유는 어떤 수든지 최소 한 개의 항으로는 나타내야 하기 때문입니다. 즉 dp[x] = 0 은 불가능합니다. 1부터 시작합니다.

n = int(input())
dp = [0 for _ in range(100001)]

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

 

www.acmicpc.net/problem/1699

1699번: 제곱수의 합