[DP] 백준 #1699 제곱수의 합 - Python

🗂️ 문제

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

 

💡 접근법

제곱 수는 1, 4, 9, 16 … 등이 있다.

항의 최소 개수를 구하기 위해서는 제곱 수를 이용해야 한다.

 

한 가지 예시로 12의 경우, dp[12] = min(dp[1] + dp[11], dp[4] + d[8], dp[9] + dp[3])이다.

즉, 제곱 수를 기준으로 모든 경우의 수를 계산해서 최소가 되는 값을 저장해야 한다.

 

😎 내 코드

import sys
import math

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

dp = [100000] * (N+1)
dp[0] = 0
dp[1] = 1

for i in range(1, N+1):
    for j in range(1, int(math.sqrt(i))+1):
        dp[i] = min(dp[i], 1+ dp[i - j*j])

print(dp[N])

 

🧐 배운 점

아이디어 관점에서.. 모든 제곱 수를 기준으로 계산을 해봐야 한다는 점을 생각해낼 줄 알아야하더라.
역시 많이 풀어봐야 한다.

 

✅ 정답 확인