[Python] 백준 1699번: 제곱수의 합 풀이

 

소스코드

n = int(input())
dp = [x for x 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])

 

dp값을 1부터 n까지 하나씩 갱신해가는 방법이다. 즉 작은 방법부터 해결해 나가는 전형적인 DP문제이다.

i로 1부터 n까지 돌면서, j는 1부터 i-1까지의 수 중 제곱한 값이 i보다 크지 않아야 한다. 

dp[i] > dp[i-j*j] + 1  이 수식은 제곱수로 표현할 때 가장 항의 개수가 작은 j 를 찾는 것이다.

*즉, 예를 들어 dp[6] = dp[6 - 2*2] + 1 = dp[2] + 1이다. 여기서 1을 더해 주는 이유는 2*2 의 경우를 더한 것이기 때문이다. 2*2 로 더하는 경우 (1가지) + 나머지 dp[2] 의 경우를 더한다고 볼 수 있다.

 

예로 7을 입력했을 때 최소 항의 개수를 구해보자.

모든 수는 1의 제곱수로 구해질 수 있으므로 처음에 dp값은 1~n 까지로 초기화한다.

    0 1 2 3 4 5 6 7

dp 0 1 2 3 4 5 6 7 이다.

i가 4이고, j가 2일 때 dp[4] = 4 > dp[4 - 2 * 2] + 1 = dp[0] + 1 = 1

이므로 dp[4] 는 1로 바뀐다.

i가 5이고, j가 2일 때 dp[5] = 5 > dp[5- 2*2] + 1 = dp[1] + 1 = 2

이므로 dp[5]는 2로 바뀐다.

i가 6이고, j가 2일 때 dp[6] = 6 > dp[6- 2*2] + 1 = dp[2] + 1 = 3

이므로 dp[6]은 3으로 바뀐다.

마지막으로 i가 7이고, j가 2일 때 dp[7] =  7 > dp[7-2*2] + 1 = dp[3] + 1 = 4 이므로

dp[7]은 4가 된다.