제곱수의 합

쉬운 DP문제도 겨우 풀었던 날이다. 주말에 더 보충해서 풀 예정이다.

9를 예로 들어 보자. 1+8, 2+7, 3+6, 4+5로 구성될 수 있음으로, 다음의 수들을 이루는 제곱수의 최소 개수들을 더한 수들 중 최소값을 구해 9의 제곱수 항의 최소개수를 구했다.

시간복잡도가 O(n^3) 이었기에 pypy3로만 통과할 수 있었다.

CODE

import sys
read = sys.stdin.readline
inf=sys.maxsize
n=int(read())

dp=list(inf for _ in range(n+1))
dp[1]=1

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

풀어야 할 문제

• 스타트 택시🔥🔥
• 미네랄
• 아기 상어
• 전깃줄 -2
• 치즈🔥
• 소가 길을 건너간 이유
• 벽 부수고 이동하기
• 알 수 없는 문장
  

```