[백준-1699] 제곱수의 합

나의 코드

import sys
import math
input =sys.stdin.readline

n=int(input())

dp=[sys.maxsize]*(n+1)
dp[0]=0
dp[1]=1
for i in range(1,n+1):
    a = int(math.sqrt(i))
    if a**2==i:
        dp[i]=1
        continue
    for j in range(1,a+1):
        dp[i]=min(dp[i],dp[i-(j**2)]+dp[j**2])
print(dp[n])

수행시간: 192ms (pypy3)

---

최적 코드

import sys
input =sys.stdin.readline

n=int(input())

dp=[0]*(n+1)
for i in range(1,n+1):
    dp[i]=i
    for j in range(1,i+1):
        if j*j>i:
            break
        if dp[i] >dp[i-j*j]+1:
            dp[i]=dp[i-(j*j)]+1 # dp[j**2]=1 이다. 
print(dp[n])

수행시간: 6580ms(python) - 너무 오래걸리니 그냥 pypy로 돌리자....

---

풀이

처음에는 그리디 알로리즘으로 풀었는데 n=12일때 틀린 답이 나왔다. 그래서 다이나믹 알고리즘으로 풀었다.
j*j는 i보다 같거나 작은 제곱수로, j*j가 i를 제곱수의 합으로 나타내는 항들중 가장 큰 값인 경우에 항의 수중 가장 작은 값이 dp[i]값이 된다.
i가 제곱수일경우 dp[i]=1 이다.
따라서 dp[i-(j*j)]+dp[j*j]=dp[i-(j*j)]+1이다.

최적 코드의 경우 다른 사람들이랑 다를게 없는데 나만 시간이 2000ms더 나왔다. 그리고 j * j를 쓰지않고 j**2를 쓰면 시간초과가 났다.