문제
심마니 영재는 산삼을 찾아다닌다.
산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.
마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.
점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.
각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.
매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.
에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.
영재는 첫 번째 돌에서부터 출발한다.
입력
첫 번째 줄에는 돌의 개수 N이 주어진다.
N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다.
마지막 줄에는 K가 주어진다.
출력
산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.
제한
- 1 ≤ N ≤ 20
- 작은 점프, 큰 점프 시 필요한 에너지와 K는 5,000을 넘지않는 자연수이다.
코드
n = int(input())
energy = [[0, 0]] # i번째 돌에서 작은 점프 / 큰 점프 시 필요한 에너지
for _ in range(n-1):
energy.append(list(map(int, input().split())))
k = int(input())
if n == 1:
print(0)
exit()
if n == 2:
print(energy[1][0])
exit()
dp = [[0, 0] for _ in range(n+1)] # 큰 점프 안함 / 함
dp[2][0] = energy[1][0]
for i in range(3, n+1):
# 큰 점프 아직 안 함
dp[i][0] = min(dp[i-1][0]+energy[i-1][0], dp[i-2][0]+energy[i-2][1])
if i == 4:
dp[i][1] = k
elif i == 5:
dp[i][1] = min(dp[i-1][1]+energy[i-1][0], dp[i-3][0]+k)
elif i > 5:
dp[i][1] = min(dp[i-1][1]+energy[i-1][0], dp[i-2][1]+energy[i-2][1], dp[i-3][0]+k)
if n == 3:
print(dp[n][0])
else:
print(min(dp[n]))
dp배열의 0행에는 큰 점프를 아직 안 했을 때의 에너지 최솟값, 1행에는 큰 점프를 이미 했을 때의 에너지 최솟값을 저장해준다.
이때 n의 범위가 1 ≤ n ≤ 20이므로 예외 처리들이 좀 필요하다. 점화식을 세우는 것 자체는 별로 오래 걸리지 않았지만 예외 처리 때문에 시간이 더 걸린 것 같다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 15486번 퇴사 2 (0) | 2023.04.11 |
---|---|
[Python/파이썬] 백준 22869번 징검다리 건너기 (small) (0) | 2023.04.11 |
[Python/파이썬] 백준 10844번 쉬운 계단 수 (0) | 2023.04.10 |
[Python/파이썬] 백준 9465번 스티커 (0) | 2023.04.10 |
[Python/파이썬] 백준 17069번 파이프 옮기기 2 (0) | 2023.02.15 |