백준 1149:RGB거리

문제

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

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

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

입력

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

출력

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

풀이

모든 경우의 수를 따로 저장한다고 생각하면 접근하기 힘들 수 있다. 빨간색, 초록색, 파란색을 칠하는 비용이 각각 리스트에 저장이 되어있기 때문에, 이들을 선택하였을 때, 최선의 선택을 리스트에 업데이트해 나가면 쉽게 풀 수 있다.

첫번째 줄에는 빨간색[0][0], 초록색[0][1], 파란색[0][2]을 칠하는데 필요한 비용이 들어있다. 이것을 활용하면 된다.

• 빨간색을 선택했을 때, 할 수 있는 최선의 선택에 대한 비용을 [1][0]에 저장하고,
• 초록색을 했을 때, 할 수 있는 최선의 선택에 대한 비용을 [1][1]에 저장하고,
• 파란색을 했을 때, 할 수 있는 최선의 선택에 대한 비용을 [1][2]에 저장한다.

이러한 작업을 쭉 이어나간 다음, 제일 마지막에 나온 값들 중에서 최솟값을 고르게 된다면 그게 최소 비용이 될 것이다.

코드

N = int(input())
RGB = []

for i in range(N):
    RGB.append(list(map(int, input().split())))

for i in range(1, N):
    RGB[i][0] = min(RGB[i-1][1], RGB[i-1][2]) + RGB[i][0]
    RGB[i][1] = min(RGB[i-1][0], RGB[i-1][2]) + RGB[i][1]
    RGB[i][2] = min(RGB[i-1][0], RGB[i-1][1]) + RGB[i][2]
print(min(RGB[N-1]))