[BOJ] 1699 제곱수의 합 (Pyhton / 파이썬)

🧷 문제

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

주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제이다.

🛠 풀이

이 문제는 Bottom-Up 방식의 DP로 해결할 수 있다.

Step 1.
 먼저 DP table을 길이 n의 1차원 리스트로 만들어준다. 모든 항은 최대 i의 길이를 가지므로 (1+1+1+...+1) 값은 i로 초기화해준다.
d = [i for i in range(n+1)]

Step 2.
 주어진 숫자가 제곱수라면 제곱수 항의 최소 개수는 항상 1이므로, 1부터 i까지 제곱수들을 빼가면서 뺀 숫자 + 1과 기존의 최소 개수를 비교하여 답을 구해준다.
if dp[i] > dp[i - j*j] + 1: dp[i] = dp[i - j*j] + 1

Step 3.
 위의 방법으로 구해진 DP table의 n번째 값을 출력한다.

🖊 나의 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    dp = [i for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, i):
            if j*j > i:
                break
            if dp[i] > dp[i - j*j] + 1:
                dp[i] = dp[i - j*j] + 1

    print(dp[n])