BOJ 4957 Pollock's conjecture

문제 링크:

문제 내용

삼각수는 공을 평면에 배열하여 삼각형을 만들었을 때 필요한 공의 개수로, $a_n = \frac{n(n+1)}{2}$입니다.

이와 비슷하게 사면체수를 정의할 수 있습니다. 사면체수는 공을 3차원에 쌓아서 사면체를 만들었을 때 필요한 공의 개수로, $b_n = \frac{n(n+1)(n+2)}{6}$입니다.

양의 정수 $N$이 주어질 때, $N$을 사면체수의 합으로 나타내기 위해 필요한 사면체수의 최소 개수와, 홀수 사면체수의 합으로 나타내기 위해 필요한 홀수 사면체수의 최소 개수를 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 0으로 종료됩니다.

각 테스트 케이스에 대해, $N$의 값이 한 줄에 주어집니다. ($1 \le N \le 10^6$)

출력

각각의 $N$에 대해, 문제의 답을 순서대로 한 줄에 출력합니다.

문제 풀이

DP = [inf] * 1000001
DP[0] = 0
for b_i in 사면체수들:
    for i in b_i..=1000000:
        DP[i] = min(DP[i], DP[i - b_i] + 1)