문제링크

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

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

풀이

두번째 집부터 보자면
두번째집을 빨간색으로 칠할경우
첫번째 집은 파란색, 초록색중에 하나를 칠했다고 볼수 있기 때문에
첫번째 집의 파란색, 초록색의 최소값을 두번째 집의 빨간색에 더해준다.

초록색, 파란색의 경우도 마찬가지로
이전 집에서 칠할 수 있는 최소값을 더해주는 방식으로

밑으로 내려갈수록 색칠할수 있는 최소값을 더해나가
가장 끝집의 최소값을 구하면
전체 최소값을 구한것이 된다.

input = __import__('sys').stdin.readline

n = int(input())
li = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
    for j in range(3):
        a, b, c = li[i-1]
        if j == 0:
            temp = min(b, c)
        elif j == 1:
            temp = min(a, c)
        else:
            temp = min(a, b)
        li[i][j] += temp
print(min(li[-1]))

해당 문제를 풀었다면
1932번: 정수삼각형 문제를 추천한다.
https://www.acmicpc.net/problem/1932