문제
N행 3열 격자에서 첫 행 가운데에서 마지막 행 가운데까지의 최소 비용 경로를 구하라. 이동은 아래/아래좌/아래우/같은 행 우측으로 가능하다.
입력
여러 테스트 케이스가 주어지며, 각 케이스에 행 수 N과 N x 3 격자 값이 주어진다. N=0이면 종료.
출력
각 케이스마다 k. result 형식으로 최소 비용을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 13 7 5 7 13 6 1 -7 100 0 -1 1 0 | 1. 11 |
풀이
3열 DP로 각 행의 최소 비용을 이전 행과 같은 행의 왼쪽 값으로부터 갱신한다.
- 첫 행에서 가운데(1열)를 시작점으로 초기화한다
- 각 행의 0열은 이전 행의 0열, 1열 중 최솟값에서 온다
- 1열은 이전 행의 0/1/2열과 같은 행 0열에서, 2열은 이전 행의 1/2열과 같은 행 1열에서 온다
- 마지막 행의 1열 값이 답이다
핵심 아이디어: 3열 고정이므로 행당 O(1) 전이로 O(N) 시간에 해결된다. 같은 행 좌→우 이동이 가능하므로 열 순서대로 갱신해야 한다.
코드
import sys
input = sys.stdin.readline
K = 1
while True:
N = int(input())
if not N:
break
dp = []
for i in range(N):
dp.append(list(map(int, input().split())))
ans = 0
dp[1][0] += dp[0][1]
dp[1][1] += min(dp[0][1], dp[0][1] + dp[0][2], dp[1][0])
dp[1][2] += min(dp[0][1], dp[0][1] + dp[0][2], dp[1][1])
for i in range(2, N):
dp[i][0] += min(dp[i - 1][0], dp[i - 1][1])
dp[i][1] += min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i][0])
dp[i][2] += min(dp[i - 1][1], dp[i - 1][2], dp[i][1])
print("%d. %d" % (K, dp[N - 1][1]))
K += 1복잡도
- 시간: O(N)
- 공간: O(N)