DynamicProgramming1_23징검다리건너기(21317)

문제

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

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

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

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

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

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

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

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

입력

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

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

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

출력

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

풀이

1. 1번 돌부터 각 N번 돌까지의 최소 에너지를 저장할 dp배열을 생성한다.
2. 매우 큰 점프 없이 작은 점프와 큰 점프만을 사용하여 최솟값을 갱신한다.
3. 위에서 만들어진 dp배열에 매우 큰 점프를 모든 경우에 적용해보며 그 때마다 마지막 돌까지의 최소 에너지를 계산하여 N번 돌의 최솟값을 갱신한다.
4. 최종으로 도출된 N번 돌까지의 최소 에너지를 반환한다.

코드

import sys
sys.stdin = open ("input.txt", "rt")
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)

배운 것

코멘트