[python] 1699. 제곱수의 합

 

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

 

풀이

 

이전에 작성한 문제와 동일한 유형의 문제입니다. 

 

문제 풀이는 이 게시글을 확인해주시기 바랍니다.

https://esjeong153.tistory.com/96

[python] 17636. Four Squares

 

해당 게시글에 풀이과정이 설명되어 있기 때문에,

풀이과정의 설명 없이 바로 코드를 공유하도록 하겠습니다.

 

 

 

n = int(input())
dp = [i for i in range(n+1)]

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

print(dp[n])