[백준, 파이썬, 21317번] 징검다리 건너기

풀이

 

• DP를 활용해서 나름 괜찮게 접근하고 풀었다고 생각했는데 
• 뭔가 조금 꼬여서 시간이 꽤 걸렸다.
• 우선 처음에는 작은 점프, 큰 점프, 매우 큰 점프를 한번에 순회하면서 조회하려 했지만
• 반례는 맞지만 제출이 안되어서
• 따로 분리하여 풀이를 했음.
• 그래서 작은, 큰 점프를 우선 진행한 다음 매우 큰 점프를 적용한 코드를 후에 적용

 

import sys

input = sys.stdin.readline

n = int(input())

jump = [list(map(int,input().rstrip('\n').split())) for _ in range(n-1)]

dp = [sys.maxsize]*n

dp[0] = 0

for i in range(n-1):

    if i+1<n: dp[i+1] = min(dp[i+1],dp[i]+jump[i][0])

    if i+2<n: dp[i+2] = min(dp[i+2],dp[i]+jump[i][1])

s_jump = int(input())

result = dp[-1]

for i in range(3,n):

    b_val, one, two = dp[i-3]+s_jump, sys.maxsize, sys.maxsize

    for j in range(i,n-1):

        if j+1<=n: one = min(one,b_val+jump[j][0])

        if j+2<=n: two = min(two,b_val+jump[j][1])

        b_val, one, two = one, two, sys.maxsize

    result = min(result, b_val)

print(result)