[알고리즘] 백준 - 1149 RGB 거리 파이썬 구현

설명

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

 

해설

 아래와 같이 집1, 집2, 집3인 경우의 R,G,B 페인트를 칠하는 비용이 있다고 가정한다.

Dynamic programming은 이전 계산값을 저장해서 다음 계산에 사용한다고 생각할 수 있다.

아래 그림을 보면 위에서 만든 자료구조를 가지고 같은 모양(열과 행이 같은) 자료구조를 만들어 자료를 업데이트 하는 것을 볼 수 있다.

업데이트를 하는 과정은 아래와 같다.

1. 각 샐은 현재 집을 해당 컬럼(R,G,B)로 칠했을때의 최소 비용이다.

2. 집2에 빨간색을 칠하는 경우 : 집2를 빨간색으로 칠하는 비용 + 최소값(집1을 초록색으로 칠하는 경우, 집 1을 파란색으로 칠하는 경우)

    집2에 파란색을 칠하는 경우 : 집2를 파란색으로 칠하는 비용 + 최소값(집1을 초록색으로 칠하는 경우, 집 1을 빨간색으로 칠하는 경우)

위 2개의 규칙을 따라서 전체 셀을 업데이트 한다.

마지막까지의 최소비용을 구하면 해당 row에서 가장 최소인 값을 출력해주면된다.

 

코드

 

def min(a, b):
    return a if a <= b else b
#RGB를 빨,초,파
#이웃은 같은색이 안됨 i의 이웃은 i-1, i+1
#빨강 비용, 초록 비용, 파랑 비용이 주어질때 최소로 칠 할 수 있는 비용
 
#집의 수
n = int(input())
matrix = [[0]*3 for i in range(n)]
 
 
for i in range(n):
    #각 색별 페인트 비용
    matrix[i][0], matrix[i][1], matrix[i][2] = map(int, input().split())
 
matrix2 = [[0]*3 for i in range(n)]
 
for i in range(n):
    if i == 0:
        matrix2[i] = matrix[i]
    else:
        matrix2[i][0] = matrix[i][0] + min(matrix2[i-1][1], matrix2[i-1][2])
        matrix2[i][1] = matrix[i][1] + min(matrix2[i-1][0], matrix2[i-1][2])
        matrix2[i][2] = matrix[i][2] + min(matrix2[i-1][0], matrix2[i-1][1])
 
print(min(min(matrix2[n-1][0], matrix2[n-1][1]), matrix2[n-1][2]))