[BOJ/Python] 백준 1660 - 캡틴 이다솜

문제

문제

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

예를 들어, 사이즈가 3크기의 한 더미 모양은 다음과 같다.

  X

 

  X

 X X

 

  X

 X X

X X X

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

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

 

입력

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

 

출력

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

풀이

import sys
input = sys.stdin.readline

N = int(input())
li = []
a = 0
idx = 1
while a < N:
    a += (idx * (idx + 1)) // 2
    li.append(a)
    idx += 1
dp = [999999] * (N + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, N + 1):
    for a in li:
        if a > i: break
        dp[i] = min(dp[i], 1 + dp[i - a])
print(dp[N])

1 3 6 10 15 ...
1 4 10 20 35 ...

n = 1 -> 1
n = 2 -> 2
n = 3 -> 3

n = 4 -> 1
n = 5 -> 2
n = 6 -> 3
n = 7 -> 4

n = 8 -> 2
n = 9 -> 3

a = 1 i = 2인 경우:
dp[2] = min(dp[2], 1 + dp[1])
dp[2] = 2

dp[3] = min(dp[3], 1 + dp[2])
dp[3] = 3

a = 4 i = 2인 경우:
break

a = 4 i = 4 -> 1 or 4(min: 1)인 경우:

dp[4] = min(dp[4], 1 + dp[3]) = 4
dp[4] = min(dp[4], 1 + dp[0]) = 1

 

1. dp 배열의 초기값을 임의의 큰 수로 지정
2. dp[0], dp[1]을 초기값으로 지정: N이 자연수이기 때문에 무조건 존재함
3. a부터 N까지 반복문을 돌면서 점점 추가되는 더미의 개수를 리스트에 저장
   (수열을 구한 뒤 기존 값에 += 되는 값을 리스트에 추가함)
4. i = 2부터 주어진 N값을 돌면서 + 리스트 내부의 a값 이중 반복문을 돌면서 dp 배열 값 변경
5. a = 4, i = 4의 경우 중단점이 변경되는데, 사면체를 2층으로 쌓아 1개로 만드는 것이 가장 최소 개수이므로 i = 4, a = 4인 경우가 가장 최소값이다. 따라서 a보다 i가 더 커지는 경우 break를 주어 반복문을 중단해야 함