백준 1699 제곱수의 합

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다. 이 경우, 수학자 소크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오

풀이

처음 문제를 접근할 땐 주어진 숫자보다 작은 가장 큰 제곱 수부터 차례대로 구하면서 풀었다.
하지만 가장 큰 제곱 수부터 차례대로 구하는 방식이 항의 갯수를 최소한으로 한단 보장을 하지 못한다.
즉 DP 문제이다.

핵심

아래는 1부터 7까지의 최소 제곱 항의 수이다.

|1|2|3|4|5|6|7|
|—|—|—|——|—|—|—|—|—|
|1|2|3|1|2|3|4|4|

1~3까지는 1의 합으로 최소 항을 구할 수 있다.
2는 1+1이다. 이는 dp[1]+1이다.
3은 1+1+1이다. 이는 dp[2]+1
4는 1+1+1+1, 2^2로 나타낼 수 있다. 이는 dp[0]+1 또는 dp[3]+1이다.

즉 dp[i]는 dp[i-n^2]+1 들의 최솟 값이다. (n은 주어진 숫자의 1/2 제곱 수)

코드

import sys

num = int(sys.stdin.readline())
dp = [i for i in range(num+1)]

for i in range(4,num+1):
    pow = int(i**0.5)
    for j in range(1,pow+1):
        dp[i]=min(dp[i],dp[i-j*j]+1)

print(dp[num])