[ 백준 / Pyhton ] #1699 제곱수의 합

문제

 

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

1699번: 제곱수의 합

---

Algorithm

해당 자연수가 몇 개의 제곱수의 합으로 나타낼 수 있는지 찾는 문제이다.

먼저, 해당 자연수가 제곱수라면 1개의 제곱수의 합으로 나타낼 수 있으므로 제곱수를 판단해야 한다. 따라서 math모듈을 이용하여 제곱수 판별 함수를 만들었다.

#제곱수 확인 함수 제곱수면 1을 return.
def decide(n):
    if math.sqrt(n).is_integer():
        return 1
    else:
        return -1

해당 자연수에 루트를 씌웠을 때 integer이면 1을 return한다.

DP문제이므로, 해당 자연수가 몇 개의 최소항으로 나타낼 수 있는지를 담는 DP배열을 선언해준다.

그후, 반복문을 통해 2부터 n까지 돌면서 제곱수면 해당 DP배열에 1을 넣어준다.

해당 자연수가 제곱수가 아니면, 1 4 9 16 .. 과 같은 제곱수를 빼준 DP배열의 index들중 최솟값을 해당 DP배열에 적용시키면 된다.

while문을 통해 j의 제곱이 해당 자연수보다 작을때까지 반복하고, temp라는 임시 배열에 넣어서 그중의 최솟값을 DP배열에 넣어준다.

그 후에 DP배열의 해당 자연수 index값을 출력해주면 된다.

---

 

 

Code

input = __import__('sys').stdin.readline
import math

#제곱수 확인 함수 제곱수면 1을 return.
def decide(n):
    if math.sqrt(n).is_integer():
        return 1
    else:
        return -1

n = int(input())

dp = [0]*(n+1)
dp[1] = 1

for i in range(2,n+1):
    if (decide(i) == 1):
        dp[i] = 1
    else:
        temp = []
        j = 1
        while(j**2 < i):
            temp.append(dp[i-(j**2)]+1)
            j+=1
        dp[i] = min(temp)

print(dp[n])