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

풀이

문제를 보자마자 이코테에 나온 개미 전사 문제가 떠올랐다. 개미전사는 1차원이고 이건 2차원이라는 점이 조금 다르다.

현재 집에서 R(0)을 선택했을 경우 다음 집은 G(1), B(2)를 선택 할 수 있다.
현재 집에서 G(1)을 선택했을 경우 다음 집은 R(0), B(2)를 선택 할 수 있다.
현재 집에서 B(2)을 선택했을 경우 다음 집은 R(0), G(1)를 선택 할 수 있다.
현재 집에서 선택한 색의 비용과 다음 위치에서 가능한 비용 중 최소 비용의 합을 누적해서 저장한다.

코드

import sys
input = sys.stdin.readline
n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]

for house in range(1, n):
    for color in range(3):
        cost[house][color] = cost[house][color] + min(cost[house-1][(color+1)%3], cost[house-1][(color+2)%3])
print(min(cost[-1]))