[백준/Python] 21317번: 징검다리 건너기

문제

https://www.acmicpc.net/problem/21317

21317번: 징검다리 건너기

---

문제 요약

N개의 돌이 일렬로 나열되어 있는 강가에서 마지막 돌에 산삼이 있다.

 

첫 번째 돌에서부터 출발하여 마지막 돌까지 산삼을 캐기 위해 돌과 돌 사이를 점프하며 이동해야한다.

 

점프의 종류

1. 현재 위치에서 다음 돌로 이동하는 작은 점프

2. 1개의 돌을 건너뛰어 이동하는 큰 점프

3. 2개의 돌을 건너뛰어 이동하는 매우 큰 점프 (1번만 사용 가능)

 

점프를 할 때는 점프를 하는 돌의 번호마다 다른 에너지가 소비된다.

 

매우 큰 점프는 돌의 번호와 상관없이 k만큼의 에너지가 소비된다.

 

산삼을 얻기 위해 필요한 에너지의 최솟값을 구한다.

---

코드

N = int(input()) # 돌 개수

dp = [5000 * 20] * N
# dp[i]는 i번 돌까지 도착하는데 필요한 최소 에너지

# energy[i][0]은 i번 돌에서 작은 점프를 했을 때 소비되는 에너지
# energy[i][1]은 i번 돌에서 큰 점프를 했을 때 소비되는 에너지
energy = []
for _ in range(N - 1):
    energy.append(list(map(int, input().split())))

k = int(input())
# 매우 큰 점프를 하는데 발생하는 에너지

if N == 1: # 돌이 1개가 주어지면
    print(0) # 에너지를 사용하지 않아도 된다.
    exit()

dp[0] = 0
dp[1] = energy[0][0]

# 작은 점프. 큰 점프만 사용했을 때 dp[i] 생신
for i in range(2, N):
    dp[i] = min(dp[i-1] + energy[i-1][0], dp[i-2] + energy[i-2][1])

# 매우 큰 점프가 사용되는 것이 가능한 위치에서 더 적은 비용이 발생하면 갱신
for i in range(3, N):
    k_e, dp1, dp2 = dp[i-3]+k, 5000 * 20, 5000 * 20
    # k_e는 i-3 위치에서 매우 큰 점프를 사용하여 i 위치로 이동했을 때 발생한 에너지 (초기값)
    # dp1, dp2는 작은 점프, 큰 점프를 사용했을 때의 에너지
    for j in range(i, N - 1): 
    # i- 3 위치에서 매우 큰 점프를 사용하고 j 위치에 도달했을 때의 최소 에너지 갱신 (j는 i 다음 위치들)

        #print(f"{j}에 도달! k_e는{k_e}, dp1은 {dp1} dp2는 {dp2}")
        dp1 = min(dp1, k_e + energy[j][0])
        dp2 = min(dp2, k_e + energy[j][1])

        # 즉 k_e는 매우 큰 점프 사용을 포함하여 현재 위치 j까지 왔을 때 최소 비용 에너지
        # dp1은 매우 큰 점프 사용을 포함하여 다음 위치 j + 1까지 까지 왔을 때 최소 비용 에너지
        # dp2는 매우 큰 점프 사용을 포함하여 다음 다음 위치 j + 1까지 왔을 때 최소 비용 에너지

        k_e, dp1, dp2 = dp1, dp2, 5000 * 20 # 위치를 한 칸씩 이동하여 갱신

    dp[-1] = min(dp[-1], k_e)
    # 위 반복문으로 마지막 위치에 도달했을 때 에너지 k_e (매우 큰 점프를 사용)와 비교하여 갱신

print(dp[-1])

---

코드 설명

+ 돌이 1개가 주어지면 에너지를 사용하지 않아도 되므로 0을 출력하고 프로그램을 종료한다.

 

1. i번 돌까지 도착하는 데 필요한 최소 에너지를 저장하는 메모이제이션 테이블 dp[i]를 생성한다.

 

2. 먼저 매우 큰 점프를 사용하지 않고 도달할 수 있는 최소 비용을 구한다.

+ i - 1번 돌까지 발생한 최소 에너지에서 작은 점프를 사용한 에너지와, i - 2번 돌까지 발생한 에너지에서 큰 점프를 사용한 에너지를 비교하여, i번 돌까지 도착하는 데 필요한 최소 에너지 비용으로 갱신한다.

 

3. 매우 큰 점프를 사용하여 마지막 돌에 도착했을 때 더 작은 비용이 발생할 수 있는지를 파악하고 갱신한다.

 

3 - 1. i - 3번 돌에서 매우 큰 점프를 사용하고 i 위치에 도달했을 때의 최소 에너지(k_e)를 파악한다. 

 

3 - 2. 현재 위치 j (j >= i) 에서 작은 점프, 큰 점프를 사용하여 j + 1, j + 2 위치에 도달했을 때 최소 에너지(dp1, dp2)를 파악한다. 

 

3 - 3. 현재 위치 j를 한 칸씩 이동시키며 위치에 맞는 최소 비용으로 갱신한다.

+ k_e => dp1

+ dp1 => dp2

+ dp2 => 나올 수 없는 최대 에너지 비용 (5000 × 20)

 

3 - 4. k_e를 마지막 위치까지 이동시켰다면 매우 큰 점프를 사용하지 않고 마지막 위치까지 도착할 때 발생한 비용과 비교하여 dp[-1]값을 갱신한다.

 

4. dp[-1] 값을 출력한다.