[백준_1699] 제곱수의 합 python

dp[12],,

그를조심해,,

# 입력 속도 개선
import sys
input = sys.stdin.readline

# n 입력
n = int(input())

# dp 설계
dp = [
    0 for _ in range(n+1)
]

# 제곲값들 넣어줄 리스트 만들기
s = [i**2 for i in range(1, 317)]

# dp 채워넣기
for i in range(1, n+1):

    # 최솟값 담아줄 리스트
    min_list = []

    # 1 ~ i 사이까지의 j 값 중
    for j in s:

        # 뺄 제곱수가 i보다 크다면
        if j > i:
            break

        # 뺄 제곱수가 i보다 작다면
        # 최솟값 후보리스트에 올리기
        min_list.append(dp[i-j])

    # dp에 추가해줄 값 선정 후  + 1
    dp[i] = min(min_list) + 1

# 출력
print(dp[-1])