[백준 파이썬] 1149번 RGB거리

다이나믹 프로그래밍

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

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

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

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

입력
- 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다.
- 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력
- 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

입력예시1                                                 출력예시1
3                                                                96
26 40 83
49 60 57
13 89 99

입력예시2                                                 출력예시2
3                                                                3
1 100 100
100 1 100
100 100 1

입력예시3                                                 출력예시3
6                                                                208
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

sol) 두번째 부터는 집이 연속된 색상을 가지지 말아야하므로
현재의 rgb[i][0](i번째 집을 빨강으로 칠했을 때) rgb[i-1][1]과 rgb[i-1][2] 중
작은 값을 넣어 구한다. 이를 초록, 파랑 집에도 똑같이 적용 => 결국 이 중 최솟값 선택

n = int(input())
rgb = []  #빨강, 초록, 파랑으로 칠하는 비용에 대한 리스트

for i in range(n):  #n개의 집에 대해 빨강, 초록, 파랑으로 칠하는 비용 입력 받기
    rgb.append(list(map(int, input().split())))

for i in range(1, len(rgb)):
    #0은 빨강, 1은 초록, 2은 파랑
    rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) + rgb[i][0]  #i번째 집을 빨강으로 칠했을 때의 최솟값
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]  #i번째 집을 초록으로 칠했을 때의 최솟값
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]  #i번째 집을 파랑으로 칠했을 때의 최솟값

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