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

이전에 풀었던 예쁜 수 였던가? 굉장히 유사했던 것 같다.

결국은 Dynamic Programming이 얼만큼 이전 정보를 유용하게 활용할 것인지? 를 묻는 상황이므로,

이 부분을 잘 컨트롤 할 필요가 있겠다.

 

 

이 문제 같은 경우에는, 2가지 스텝으로 나눠서 풀면 된다.

 

첫번째로, 사면체로서 가능한 패턴인 숫자들을 구해주는 것이 되겠다.

이를 구하기 위해서는 각 step의 삼각형을 구성하기에는 몇개의 대포알이 필요한지 알아낼 필요가 있겠다.

 

이는 생각보다 쉽다. $n$번째 단의 삼각형을 만드는 것에 필요한 대포알은 $n(n + 1) / 2$개이라는 것을 쉽게 알 수 있다.

1, 3, 6, 10... 이런 Typical한 패턴을 주는 것에 유의하자.

 

그렇다면 사면체는 어떠한가? 1~n번째 단을 만드는데 필요한 대포알을 전부 합치면 되겠다.

수식으로 나타내게 된다면, 

$$\sum_{i =1}^n \frac{n(n + 1)}{2}  = \frac{1}{2} \sum_{i=1}^n n(n+1) = \frac{1}{2} (\sum_{i=1}^n n^2  + \sum_{i=1}^n n)$$

$$ = \frac{n(n+1)(2n +1)} {12} + \frac{n(n+1)}{4} = \frac{n(n + 1)(2n+1) + 3n(n+1)}{12} $$

$$= \frac{2n(n+1)(n+2)}{12} = \frac{n(n+1)(n+2)}{6}$$

이런 식으로 나올수는 있겠지만 .... 사실은 프로그래밍 안에서는 그냥 리스트 2개 만들어서 하는 편이 훨씬 낫다 ...

 

두번째 단계는, 결국 최소 step을 구하고자 하는 상황이므로, dp 리스트를 만들어 두고, 하나씩 추가하는 방식으로 진행하면 좋겠다.

비슷한 유형으로, 예쁜수가 있겠다. (https://pjw9777.tistory.com/102)

 

import sys
input = sys.stdin.readline

N = int(input())
bullet, bullet_sum = [1], [1]
cnt = 2

while bullet_sum[-1] <= N:
    bullet.append((cnt * (cnt + 1)) // 2)
    bullet_sum.append(bullet_sum[-1] + bullet[-1])
    cnt += 1

dp = [N for _ in range (0, N + 1)]

for i in range (0, len(bullet_sum)-1):
    dp[bullet_sum[i]] = 1
    for j in range (bullet_sum[i] + 1, N + 1):
        dp[j] = min(dp[j - bullet_sum[i]] + 1, dp[j])

print(dp[-1])

 

 

 

 

처음에는 그냥 python으로 풀었는데, 이후 Pypy로 푸니 어마무시하게 줄어들은 것을 확인할 수 있었다.

대신 메모리는 많이 잡아 먹었지만 .....