[백준] 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보다 작거나 같은 자연수이다.

출력

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

풀이

예제입력 5가 최소값을 구하는 과정은 다음과 같습니다.

예제 5의 최소값을 구하기 위해서는 박스1의 최소값과 [60, 66, 19]의 최솟값을 더해야합니다.
박스 1의 최소값을 구하기 위해서는 박스2의 최소값과 [45, 25, 29]의 최솟값을 더해야합니다.
다음과 같은 과정이 반복된다면 결국에는 처음 입력값인 [65, 13, 15] 의 최솟값을 구하고 다음 입력값의 최솟값을 더해주면 됩니다.

하지만 N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. 는 조건이 있으므로 다음입력값이 R일때 G일때 B일때 이렇게 3가지 경우로 나누어 계산해야합니다.
2번째 입력값이 R(32)일때 이전 입력 값인 G(39)와 B(44)의 값을 비교하여 최소값을 구하고 현재 자신의 값과 더해주는 방식으로 계산을 진행합니다.

코드

n = int(input())
a = [0]*n

for i in range(n):
    a[i] = list(map(int,input().split()))
    
for i in range(1,n): # 1부터 시작하는 이유는 다음 입력값이 이전 입력값의 최소값을 사용하기때문이다
    a[i][0]= min(a[i-1][1],a[i-1][2]) + a[i][0]
    a[i][1]= min(a[i-1][0],a[i-1][2]) + a[i][1]
    a[i][2]= min(a[i-1][0],a[i-1][1]) + a[i][2]

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