[백준 21317번] 파이썬 - 징검다리 건너기

백준 21317 - 징검다리 건너기

시간 제한 1초, 메모리 제한 1024MB

# 조건

• 심마니 영재는 산삼을 찾아다닌다.
• 산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.
• 마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.
• 점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.
• 각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.
• 매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.
• 에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.
• 영재는 첫 번째 돌에서부터 출발한다.

입력

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

출력

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

제한

• 1 ≤ N ≤ 20
• 작은 점프, 큰 점프 시 필요한 에너지와 K는 5,000을 넘지않는 자연수이다.

# 접근 방법

• 이전의 점프 값에 따라 최적의 결과가 달라지므로 다이나믹 프로그래밍 (dp)를 활용해주면 된다.
• 이 문제에서 제일 핵심은 매우 큰 점프를 언제 사용하냐가 핵심이다.
• 따라서, dp배열의 구성은 [[float('inf'), float('inf')] for _ in range(N+1)]
  • 전체 크기는 돌의 개수
  • 2차원 배열의 0번 인덱스는 작은 점프와 큰 점프만 사용한 경우
  • 1번 인덱스는 큰 점프를 사용한 경우로 구성해준다.
• 출발 지점인 [1][0]을 0으로 초기화 해주고 2번돌부터 출발해준다.
• 0번 인덱스의 dp식은 작은 점프와 큰 점프만 사용하는 경우를 비교해주면 된다.
  • 직전 돌에서 작은 점프한 값 + dp에 기록된 직전 돌의 0번 인덱스 값,
  • 2개 이전에서 큰 점프 값 + dp에 기록된 2개 이전의 돌의 0번 인덱스 값을 비교해주면 된다.
  • dp[i][0] = min(dp[i-1][0] + jump[i-1][0], dp[i-2] + jump[i-2][1])
• 1번 인덱스의 dp 식은 이미 매우 큰 점프를 사용한 경우 또는 지금 매우 큰 점프를 사용하는 경우를 비교해주면 된다.
  • 직전 돌에서 작은 점프한 값 + dp 직전돌의 1번 인덱스값
  • 2개 전의 돌에서 큰 점프 값 + dp 2개 전의 돌의 1번 인덱스 값
  • dp 3개 이전의 돌의 0번 인덱스 + K 만큼의 매우 큰 점프를 사용
• 이후 N번째 돌에서 작은 값을 출력해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
dp = [[float('inf'), float('inf')] for _ in range(N+1)]  
dp[1][0] = 0  
jump = [[0,0] for _ in range(N)]  
for i in range(N-1):  
    a, b = map(int, input().split())  
    jump[i+1] = [a,b]  
K = int(input())  
for i in range(2, N+1):  
    dp[i][0] = min(dp[i-1][0] + jump[i-1][0], dp[i-2][0] + jump[i-2][1])  
    dp[i][1] = min(dp[i][1], dp[i-3][0] + K, dp[i-1][1] + jump[i-1][0], dp[i-2][1] + jump[i-2][1])  
print(min(dp[-1]))