1699번 파이썬

반복문이 많아서 pypy로 제출했다..!

문제는 해당 숫자보다 낮은 제곱수를 전부 다 구해서(첨에 바로 직전의 제곱수만 구하면 되는 줄 알았는데 그것보다 작은 값도 최소가 될 수 있는 경우가 존재)

그 중 가장 작은 갯수를 가지는 p값에 1을 더해서 p[num]에 저장한다.

import sys
input = sys.stdin.readline
n = int(input())

p = [0 for _ in range(100001)]
p[1]=1
if n>=2:
  p[2]=2
if n>=3:
  p[3]=3
for num in range(4,n+1):
  temp=[]
  for i in range(1,317):
    k = pow(i,2)
    if num < k:
      break
    temp.append(p[num-k])
  p[num]=min(temp)+1
print(p[n])