[백준] 1149 RGB거리 python

문제

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

출력

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

코드

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

for i in range(1,n):
    #R
    rgb[i][0] = min(rgb[i-1][1], rgb[i-1][2]) + rgb[i][0]
    #G
    rgb[i][1] = min(rgb[i-1][0], rgb[i-1][2]) + rgb[i][1]
    #B
    rgb[i][2] = min(rgb[i-1][0], rgb[i-1][1]) + rgb[i][2]
print(min(rgb[n-1]))

풀이

빨강, 초록, 파랑 순으로 집 비용이 있다.

조건을 따지고 보면 전 집의 색을 제외한 다른 색 중 가장 작은 비용의 색으로 칠하면 된다.

 

index 가 0은 제외하고

1부터 반복문을 색별로 돌면 된다.

#R
rgb[i][0] = min(rgb[i-1][1], rgb[i-1][2]) + rgb[i][0]

설명해보면, i가 1이라고 해보자.

rgb[1][0] 1번집의 빨간색으로 칠하는 비용은, 전 집인 0번째 집은 빨간색으로 칠하면 안된다. 

0번째 집의 비용은 초록 rgb[0][1], 파랑 rgb[0][2] 중 작은 비용을 선택하고 현재 1번집의 빨간색 비용을 더한 값이 rgb[1][0] 이 되겠다.