[백준 1699][파이썬] 제곱수의 합

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

1699번: 제곱수의 합

 

일단 dp[i]의 값을 i를 제곱수들의 합으로 표현할 때 최소 개수로 정한다.

 

그렇게 되면 dp[i]의 값은

 

dp[1] + dp[i-1]

dp[2] + dp[i-2]

dp[3] + dp[i-3]

.

.

.

 

위 값들 중 가장 작은 값이 된다.

 

처음엔 위 방식으로 이중 반복문을 돌려서 답을 구했으나 시간 초과가 발생했다.

 

시간을 더 줄일 수 있는 알고리즘을 사용해야한다.

 

먼저 항의 개수가 최소가 되는 조건을 찾아야한다.

 

1, 4, 9 같은 제곱수의 경우 무조건 최소 항의 개수가 1이다.

 

그러므로 dp[i]의 값을 구할 때

 

dp[1] + dp[i-1]

dp[4] + dp[i-4]

dp[9] + dp[i-9]

.

.

.

 

위와 같이 제곱으로 건너뛰면 더욱 빠르게 구할 수 있다.

n = int(input())
dp = [1e9]*(n+1)
dp[1]=1
sq=[1]
for i in range(2, n+1):
    if int(i**0.5)**2==i:
        sq.append(i)
        dp[i]=1
    else:
        for j in sq:
            dp[i]=min(dp[i],dp[j]+dp[i-j])
print(dp[n])