백준 문제 중 1699번, DP, ‘제곱수의합’

백준 문제 중 1699번

https://www.acmicpc.net/problem/1699

문제

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

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

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

---

풀이

문제의 핵심은 제곱수들의 합중 어떤게 제일 최소의 항을 가지는지 판별하는 방법이다.

주어진 n의 제곱수의 합중 최소의 항개수를 dp[n]이라 할때 예시를 몇개 살펴보자.

• 1 : 1^2
• dp[1] = 1
• 2 : 1^2 + 1^2
• dp[2] = dp[1] + dp[1]
• 3 : 1^2 + 1^2 + 1^2
• dp[3] = dp[2] + dp[1]
• 4 : 2^2
• dp[4] = 1
• 5 : 2^2 +1^2
• dp[5] = dp[2^2] + dp[1]
• 6 : 2^2 + 1^2 + 1^2
• dp[6] = dp[5] + dp[1]
• 8 : 2^2 + 2^2
• dp[8] = dp[2^2] + dp[2^2]
• 9 : 3^2
• dp[9] = 1

… …

• 13 : 3^2 + 2^2
• dp[13] = dp[9] + dp[4]

… …

• 41: 5^2 + 4^2
• dp[41] = dp[25] + dp[16]

n이 주어졌을 때 1 ~ n사이의 수 i에 대하여 모든 dp[i]를 살펴보는데 i가 자연수의 제곱일 때는 dp[i] = 1을 대입하고, 제곱이 아닐때는 i보다 작거나 같은 최대 제곱수를 j라 하자. 이때 2 ~ j 사이의 수 k에 대하여 dp[i-k^2] + dp[k^2] 의 값중 최소일 때를 찾으면 그 값이 dp[i]라 할 수 있다.

이를 식으로 표현하면 dp[i] = min(dp[i-j^2] + dp[j^2], dp[i]) 라 할 수 있고 이를 코드로 구현라면 아래와 같다.

Try1

%%time
from collections import defaultdict

import math

n = int(input())

 # n보다 작거나 같은 최대의 제곱수
m = int(math.sqrt(n))

dp = defaultdict(int)

 # 제곱수에 해당하는 모든 i*i에 1 할당
for i in range(1,m+1): dp[i*i] = 1

 # dp[1] ~ dp[n]을 스캔하되 dp[i]가 0이아닌 값이 있다면 스킵
for i in range(1,n+1):
    
    if dp[i]:

        continue

     # i이하의 최대 제곱수 j    
    j = int(math.sqrt(i))

     # dp[i]에 기본값 설정
    dp[i] = dp[i-1]+1

     # 2 ~ j사이의 제곱수들의 조합 중 가장 작은 dp[i] 를 저장
    for k in range(2,j+1):
        dp[i] = min(dp[k*k]+dp[i-k*k],dp[i])

print(dp[n])

41
2
CPU times: user 8.86 ms, sys: 1.72 ms, total: 10.6 ms
Wall time: 1.89 s

이렇게 코드를 구성하고 정답처리가 됐으나 조금 더 깔끔한 방법이 없을까 검색을 해봤다.

Try2

이 문제를 처음 보고 코드를 구성할때 가장 곤란했던게 41의 처리 였다. 41은 5^2 + 4^2 의 합으로 최적화 되니 41이하의 최대 제곱수인 6^2 을 참조해서 dp를 최신화 하면 안된다.

이를 아주 깔끔하게 모든 dp를 1^2으로 나타낸 수로 초기화를 한후, 제곱수를 1부터스캔 하되
dp[i] > dp[i-j^2] + 1을 만족할때만 최신화 하게끔 설정하여 깔끔하게 처리했다. 즉 dp[41]이 이미 j=2 일때 dp[41 - 4^2] + 1로 dp[25] +1 즉 2로 설정이 되어 있어 그이후 2보다 큰 dp[i-j^2] +1 들만이 오며 이 문제가 해결됐고 가장 코드도 간결하며 실행속도 또한 가장 빨랐다.

%%time
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])

41
2
CPU times: user 10.4 ms, sys: 50 µs, total: 10.4 ms
Wall time: 1.67 s

배운점

다이나믹 프로그래밍에서 dp배열을 다룰때 dp배열에 최적의 값을 미리 넣으면 다른 값들을 쉽게 거를 수 있음을 배웠다.