[백준] 1699 '제곱수의 합' 파이썬(python)

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

1699번: 제곱수의 합

import sys
import math

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

dp = [0] * (n+1)

for i in range(1, n+1):
    dp[i] = i
    for j in range(1, int(math.sqrt(i))+1):
        if (j*j) > i :
            break
        if dp[i] > dp[i - j * j]+1:
            dp[i] = dp[i - j * j]+1

print(dp[n])

Point

• DP문제
• dp테이블을 만들고 그것의 값들을 변경해가며 푸는 문제
• range의 이해