[python] 백준 1699 : 제곱수

문제

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

1699번: 제곱수의 합

 

문제 풀이

자연수 N을 제곱수의 합으로 나타내야 하므로 

최소 개수의 제곱수로 표현하기 위해서는 

n보다 작으면서 제곱수 만큼 작은 수들 중에서

dp가 가장 작은 수를 구하면 될 것이다.

 

예를 들어 11의 최소 제곱수의 합을 구하려면

dp[11-9] , dp[11-4], dp[11-1] 에서 가장 작은 수를 택해서 1을 더하면 된다. 

 

문제는 N이 커지면서 덧셈 가능한 제곱수도 많아지기 때문에

이걸 구현하는게 조금 어려웠다^.^

length= int(input())

dp=[0]*100001
square_table=[0]*317

for i in range(1,317):
    dp[(i**2)] =1
    square_table[i] = i**2
    
square=1

for i in range(1,length+1):
    if(dp[i] == 1):
        square = i
        continue

    minimum = 100001
    for k in range(1,int(square**(1/2))+1):
        minimum = min(dp[i-square_table[k]], minimum)
       
    dp[i] = minimum+1
    
print(dp[length])

dp에 제곱수들은 미리 1을 채워넣고

square라는 변수를 통해 현재까지의 최대 제곱수를 구해서

가장 작은 dp 값을 구했다..