[알고리즘] DP유형 - 백준 1699번 파이썬

 

 

www.acmicpc.net/problem/1699

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)

 

출력

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

 

예제 입력

7

 

예제 출력

4

 

 

풀이

dp[i]를 특정 수 i를 제곱수의 합으로 표현했을 때 최소 항의 개수라고 하자.

 

우선 모든 i에 대하여 가장 최악의 경우를 살펴보면 모든 항이 1^2의 합으로만 표현된 경우이다.

이 경우는 dp[i] = i 이다.

 

그리고 제곱수(1, 4, 9, 16, ...)의 경우를 살펴보면

모든 제곱수 j는 n ^ 2로 표현할 수 있기 때문에 dp[i] = 1 이다.

 

 

그리고 몇 개의 숫자를 살펴보면 점화식을 세울 수 있다.

 

N = 11일 때

11 = 3*3 + (11 - 3*3) 

dp[11] = 1 + dp[11 - 3*3]

...

 

N = 40일 때

dp[40] = dp[40 - 1*1], dp[40 - 2*2], dp[40 - 3*3], dp[40 - 4*4], dp[40 - 5*5], dp[40 - 6*6] 중 가장 작은 값 + 1

 

여기서 +1 은 제곱수로 표현된 하나의 항을 의미한다.

 

즉, 어떤 수를 제곱했을 때 i에 가장 가까운 수를 n이라고 하고

dp리스트를 가장 최악인 경우의 값으로 초기화를 했을 때(dp[i] = i) 점화식은 다음과 같다.

dp[i] = min(dp[i], dp[i - n * n] + 1)   (단, i >= 1이며, n은 1부터 제곱했을 때 i에 가장 가까운 정수 까지)

 

코드

from math import sqrt

n = int(input())

# DP 테이블 세팅
dp = [0] * (n + 1)


# 다이나믹 프로그래밍 보텀업 방식
for i in range(1, n + 1):

	# 먼저 가장 최악의 경우인 1^2로 DP테이블 초기값을 설정
    dp[i] = i
    
    for j in range(1, int(sqrt(i)) + 1):
    	# dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        # min쓰면 시간 초과되서 if문으로 수정
        if dp[i] > dp[i - j*j] + 1:  
            dp[i] = dp[i - j*j] + 1


print(dp[n])