[백준 21317번] 징검다리 건너기 (python)

문제

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

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

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

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

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

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

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

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

 

기록

(dp 9일차) 벌써 dp만 9일째 푼다!! 근데 아직도 어렵다ㅠ 이 문제 뭔가 이해하기 어려웠다. 1번돌부터 작은점프, 큰점프, 매우 큰점프로 마지막 돌까지 가는 최솟값을 구하는 문제인데.. 입력에 대한 설명도 자세하지 않아서 헤멨다. 입력은 1번돌부터 돌에서 작은 점프하는데 소요되는 에너지, 큰 점프를 하는데 소요되는 에너지가 들어온다.

 

매우 큰 점프를 한 번밖에 뛰지 못한다는 조건 때문에 조금 고민했는데, 다른 dp문제들처럼 매우 큰 점프를 사용하지 않고 1번돌부터 각 N의 돌까지의 최솟값을 dp배열에 저장해나갔다. 그 후 dp배열에서 매우 큰 점프가 가능한 위치마다 모두 적용해보고 그 때마다 마지막 돌까지의 최솟값을 구하여 가장 작은 최솟값을 찾았다. 

 

코드

import sys
input = sys.stdin.readline

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

# dp 배열 생성
dp = [1e9]*N
dp[0] = 0
for i in range(N-1):
    s, b = map(int, input().split())
    stone.append((s, b))
    if i+1<N : dp[i+1] = min(dp[i+1], dp[i]+s)
    if i+2<N : dp[i+2] = min(dp[i+2], dp[i]+b)

# 매우 큰 점프 적용해보며 최솟값 찾기
K = int(input())
_min = dp[-1]
for i in range(3, N):
    e, dp1, dp2 = dp[i-3]+K, 1e9, 1e9
    for j in range(i, N-1):
        if i+1<=N : dp1 = min(dp1, e+stone[j][0])
        if i+2<=N : dp2 = min(dp2, e+stone[j][1])
        e, dp1, dp2 = dp1, dp2, 1e9
    _min = min(_min, e)

print(_min)

1. 1번 돌부터 각 N번 돌까지의 최소 에너지를 저장할 dp배열을 생성한다.

2. 매우 큰 점프 없이 작은 점프와 큰 점프만을 사용하여 최솟값을 갱신한다.

3. 위에서 만들어진 dp배열에 매우 큰 점프를 모든 경우에 적용해보며 그 때마다 마지막 돌까지의 최소 에너지를 계산하여 N번 돌의 최솟값을 갱신한다.

4. 최종으로 도출된 N번 돌까지의 최소 에너지를 반환한다.