🟩 [백준] [Python] Class3_17626번_Four Squares

문제

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

17626번: Four Squares

풀이

# 백준 17626번 문제 - Four Squares 
# pypy3
import sys
N = int(sys.stdin.readline())
dp = [0,1]

for i in range(2, N+1):
    min_value = 1e9
    j = 1

    while (j**2) <= i:
        min_value = min(min_value, dp[i - (j**2)])
        j += 1

    dp.append(min_value + 1)
print(dp[N])

DP를 활용하였다.