[ 21317 ] [ DP ] 징검다리 건너기

문제 설명

---

문제

심마니 영재는 산삼을 찾아다닌다.

산삼을 찾던 영재는N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.

마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.

점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.

각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.

매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.

에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.

영재는 첫 번째 돌에서부터 출발한다.

입력

첫 번째 줄에는 돌의 개수N이 주어진다.

N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다.

마지막 줄에는K가 주어진다.

출력

산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.

제한

• 1 ≤ N ≤ 20
• 작은 점프, 큰 점프 시 필요한 에너지와 K는 5,000을 넘지않는 자연수이다.

---

풀이 과정

• 2차원 DP 테이블을 구성한다.

  • DP[i][0] : i번째 돌까지의 최소비용, 매우 큰 점프 사용하지 않음.
  • DP[i][1] : i번째 돌까지의 최소비용, 매우 큰 점프 사용

• 현재 위치가 x라고 둘 때, 갈수있는 모든 돌의 비용들을 갱신한다.

  • 점프(+1)하는 경우, 큰점프(+2) 하는 경우, 매우 큰 점프(+3) 하는 경우
  • 매우 큰 점프의 경우, DP[x][1]일때는 이미 점프한 경우이므로 점프할수 없으므로, DP[x][0]에 대해서만 고려한다.

• 마지막으로, DP[N]의 최솟값을 출력해주면 된다.

  • 매우 큰점프를 사용하였거나, 사용하지 않았을 때중 최솟값

---

소스 코드

import sys
from collections import deque

N = int(input().rstrip())

small = [0] * (N+1)
big = [0] * (N+1)

for i in range(1, N):
    a, b = map(int, input().rstrip().split())
    small[i], big[i] = a, b

K = int(input().rstrip())

INT_MAX = int(10e9)
dp = [[INT_MAX] * 2 for _ in range(N+1)]
dp[1][0], dp[1][1] = 0, INT_MAX
for i in range(1, N):
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+small[i])
    dp[i+1][1] = min(dp[i+1][1], dp[i][1]+small[i])
    if i + 2 <= N:
        dp[i+2][0] = min(dp[i+2][0], dp[i][0]+big[i])
        dp[i+2][1] = min(dp[i+2][1], dp[i][1]+big[i])
    if i + 3 <= N:
        dp[i+3][1] = min(dp[i+3][1], dp[i][0] + K)


print(min(dp[N]))