[ 1660 ] [ DP ] 캡틴 이다솜

문제 설명

---

문제

캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.

각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다.

현재 다솜이의 해적선에 대포알이 N개가 있다. 다솜이는 영식이를 시켜서 사면체를 만들게 하고 싶다. 영식이는 물론 하기 싫지만 어쩔수 없이 다솜이가 시키는대로 사면체를 가능한 최소 개수 만큼 만들려고 한다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 입력 N이 들어온다. N은 300,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 영식이가 만들 수 있는 사면체 개수의 최솟값을 출력한다.

---

풀이 과정

1. 사면체가 될수있는 경우의 수를 테이블에 저장 및 DP테이블에 1로 설정한다. (최솟값이므로)
   • 즉, 경우의 수 테이블에는 [1, 4, 10, 20, ... ]이 저장된다.
   • DP[1] = 1, DP[4] = 1, DP[10] = 1, ... 이 저장된다.
2. 이후 Bottom-up 방식으로 DP테이블을 채워나가면 된다.
   • i개 대포알로 만들수 있는 최소 개수를 구할 때, 저장해 둔 경우의 수 테이블의 값들을 j라고 한다면
   • DP[i] = min(DP[i], DP[i-j[k]]) (i-j[k] > 0) 일때
3. 이후 DP[n]을 출력하면 된다.

---

소스 코드

import sys


N = int(sys.stdin.readline().rstrip())
curr = 1
step = 1
k = 1
area = 1
INT_MAX = int(10e9)
dp = [INT_MAX] * 300001
four = [1]
dp[1] = True
dp[0] = True
# 사면체 경우의 수 구하는 부분
while True:
    if N == area:
        print(1)
        sys.exit(0)
    if N < area:
        break
    k += 1
    curr += k
    area += curr
    four.append(area)
    if area <= 300000:
        dp[area] = 1

# dp 테이블 채우는 부분
for i in range(1, N+1):
    for j in four:
        if i - j > 0:
            dp[i] = min(dp[i], dp[i-j]+1)

print(dp[N])