DP 동적프로그래밍 | BOJ 백준 21317번 징검다리 건너기 | Python


created_at : 02 April 2024 - 3 mins read time
Tags: DP 동적프로그래밍

Table of Contents


BOJ 백준 21317번 징검다리 건너기 | Python

📌 백준 21317번 문제 바로가기


🔎 문제 설명

🩶 실버 1

- 난이도 ★★★★
- DP 동적프로그래밍

집중력을 잃지 않는 게 중요하다…!

사실 매우 큰 점프 1회로 제한되어 있지 않았다면 코드가 이렇게 복잡해지진 않았을 것 같다.
매우 큰 점프를 했을 때 안 했을 때 최소 에너지를 찾기 위해 리스트 2개로 알아보았다.



💻 내 코드

import sys
input = sys.stdin.readline

N = int(input())
jump = []

dp = [float('inf')] * 21
dp[0] = 0

for n in range(N-1):
    small, big = map(int, input().split())
    jump.append((small, big))
    # 매우 큰 점프를 안 하는 경우 dp
    if n+1 < N:
        dp[n+1] = min(dp[n+1], dp[n]+small)
    if n+2 < N:
        dp[n+2] = min(dp[n+2], dp[n]+big)
K = int(input())

if N == 2:
    print(jump[0][0])
elif N == 3:
    print(min(jump[0][0]+jump[1][0], jump[0][1]))
elif N > 3:
    energy_list = [dp[N-1]]

    # 매우 큰 점프를 하는 경우 dp1
    for i in range(N-3):
        dp1 = dp.copy()
        dp1[i+3] = dp1[i] + K
        for j in range(i+4, N):
            dp1[j] = min(dp1[j-2]+jump[j-2][1], dp1[j-1]+jump[j-1][0])
        energy_list.append(dp1[N-1])
    print(min(energy_list))
else:
    print(0)




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).