BOJ 1660 - 캡틴 이다솜

문제

N개의 대포알을 사면체 모양으로 쌓을 때, 필요한 최소 사면체 개수를 구하라. 사면체 수는 1, 4, 10, 20, 35, ... 이다.

입력

대포알의 개수 N이 주어진다 (1 <= N <= 300000).

출력

최소 사면체 개수를 출력한다.

예제

입력	출력
`10`	`1`

풀이

N 이하의 사면체 수를 모두 구한 뒤, 동전 교환 DP로 최소 개수를 계산한다.

삼각수의 누적합으로 사면체 수를 생성한다 (N 이하까지)
dp[i] = i를 사면체 수의 합으로 나타내는 최소 개수로 정의한다
각 i에 대해 모든 사면체 수 b를 순회하며 dp[i] = min(dp[i], 1 + dp[i-b])로 갱신한다
사면체 수와 정확히 같으면 dp[i] = 1

핵심 아이디어: 사면체 수를 동전의 액면가로 보면 전형적인 동전 교환 문제로 환원된다.

코드

import sys
 
input = sys.stdin.readline
 
n = int(input().rstrip())
balls = []
b = 0
i = 1
while b < n:
    b += (i * (i + 1)) // 2
    balls.append(b)
    i += 1
MAX = sys.maxsize
dp = [MAX] * (n + 1)
for i in range(1, n + 1):
    for b in balls:
        if b >= i:
            if b == i:
                dp[i] = 1
            break
        dp[i] = min(dp[i], 1 + dp[i - b])
print(dp[n])

복잡도

시간: O(N * T), T는 사면체 수의 개수
공간: O(N)

문제