본문 바로가기

코딩/Python

[Python] 백준 1699 제곱수의 합

반응형

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

 

1699번: 제곱수의 합

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다

www.acmicpc.net

코드 작성

import sys
input = sys.stdin.readline

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

코드  풀이

#1 점화식

점화식은 아래와 같이 구할 수 있다.

      합      :    i    =    ( i - j * j )      + ( j * j )  =  i 

항의 개수 : d[i]  = d [ i - j * j ] 개   +  1개   

 

 

# 2 예시  30의 경우

dp[30] = dp[30-5*5] +1 = dp[5] + 1

dp[5] = dp[5-2*2]+1 = dp[1] + 1

dp[1] = 1

따라서 dp[30] = dp[1] + 2 = 3

30 = 5*5 + 2*2 + 1*1

 
반응형