[BOJ, Python] 17626 - Four Squares ( with DP )

17626번: Four Squares

50000 이하의 자연수가 주어졌을 때, 해당 자연수를 최대 4개의 제곱수의 합으로 표현할 수 있다는 라그랑주의 증명을 바탕으로 한 문제이다. 뭔가 특별한 풀이법이 존재할 것 같긴 한데, 어떤 자연수 N을 다른 자연수의 제곱수의 합으로 나타낼 때 그 개수의 최댓값은 그 자신 N을 넘을 수 없고, 1부터 N까지의 답을 순차적으로 구하려했을 때 제곱 수(1, 4, 9, 16, ...)마다 1로 초기화된다는 점에서 다이나믹 프로그래밍(DP)을 활용하기로 했다.

import math

# dp 설정, 제곱수(1, 4, 9, 16, ...)에서는 무조건 그 값이 1임
dp = [1 if math.sqrt(i).is_integer() else 0 for i in range(50001)]
dp[0] = 0

n = int(input())

for i in range(2, n + 1):

# 제곱수에서는 다른 연산이 필요 없다.
    if math.sqrt(i).is_integer():
        continue
        
    # 정답의 최댓값은 그 자신보다 작을 수 밖에 없음.
    # 따라서 min_value의 초기값은 그 자신
    bf = math.floor(math.sqrt(i))
    min_value = i
    
    # 제곱 수의 값을 하나씩 줄여가며 언제 최소가 되는지 판단
    while bf > 0:
        min_value = min(min_value, 1 + dp[i - bf ** 2])
        bf -= 1
    dp[i] = min_value
    
print(dp[n])