BOJ 17626 - Four Squares

문제

백준 온라인 저지 - 17626번

풀이 과정

특정 수를 만들기 위한 최소 제곱수의 개수를 구하는 문제입니다.

만약 N 의 제곱수를 구하기 위해서는 최대 N**0.5 까지만 검사해보면 됩니다.
때문에 모든 경우의 수를 완전 탐색 하는 방법도 있을 수 있지만 이 경우 중복 검사로 인해 시간초과를 피하지 못하며
따라서 이를 최적화하기 위해 동적 계획법 을 사용해야합니다.

dp(n): n을 나타내기 위한 최소 제곱수의 개수 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다.

do(n) = min(dp(n - k^2), dp(n - (k - 1)^2), ... dp(n - 1)) + 1

코드

import sys

N = int(input())


def solution():
    dp = [-1] * (N + 1)

    dp[0] = 0
    dp[1] = 1

    for n in range(2, N + 1):
        dp[n] = sys.maxsize
        for k in range(1, int(n ** 0.5) + 1):
            dp[n] = min(dp[n], dp[n - k**2] + 1)

    return dp[N]


print(solution())