문제: https://www.acmicpc.net/problem/1149

풀이

입력을 arr에 2차원 배열로 받는다.
arr[1] 행의 각 열에 arr[0] 행의 최솟값을 더한다. (자신의 열은 제외)
arr[2] 행의 각 열에 arr[1] 행의 최솟값을 더한다. arr[1]은 이미 두 값이 더해져있으므로 arr[2]에는 최솟값 후보가 되는 세 값이 모두 더해져 있을 것이다.
이런 식으로 arr[n-1] 행까지 값을 모두 더한 후, arr[n-1] 행의 세 값 중 최솟값을 구하면 된다.

이전 행의 값을 저장해두었다가 다시 사용한다는 점에서 다이나믹 프로그래밍으로 해결하는 문제라고 할 수 있다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().strip().split())))

for i in range(1, n):
    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][0], arr[i-1][2])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])

print(min(arr[n-1][0], arr[n-1][1], arr[n-1][2]))