BOJ-17626 Four Squares

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

문제 소개

모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으며, 어떤 자연수를 복수의 방법으로 표현된다.

자연수 n이 주어질 때, 합이 n과 같게 되는 제곱수들의 최소 개수를 구한다.

문제 풀이

dp로 풀이하였다. dp[x]는 자연수 x를 표현하는 제곱수들의 최소 개수를 의미한다.

문제 소개에 따라, dp[i]은 dp[i - (j ** 2)]에 1을 더한 것과 같다.

코드에서 두번째 for문은 dp[i - (j ** 2)] 중 최솟값을 찾아 변수 target에 저장하는 동작이다.

limit은 두번째 for문의 인덱스인 j의 범위를 정하기 위한 변수이다.

dp[i - (j ** 2)]의 범위는 dp[i - 1] 부터 시작하여 i가 제곱수인 경우 dp[0]까지, i가 제곱수가 아닌 경우 dp[1]까지가 된다.

마지막으로 dp[n]을 출력한다.

코드

from sys import stdin
from math import sqrt
input = lambda: stdin.readline().rstrip()

n = int(input())
dp = [0, 1]

# dp[2] 부터 dp[n]까지 차례로 구하기
for i in range(2, n + 1):
    target = 4
    # limit으로써 j의 범위를 정함
    limit = int(sqrt(i))
    for j in range(1, limit + 1):
        target = min(target, dp[i - (j ** 2)])
    dp.append(target + 1)

print(dp[n])