백준 1149 RGB거리

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

 

 이 문제는 RGB 거리에 직선으로 나열되어 있는 집들이 빨강,초록,파랑 색 중 하나로 색칠 되는데 서로 이웃인 집의 색깔은겹쳐서는 안 되고, 집마다, 색마다 색칠하는 비용이 주어지고, 모든 집을 규칙대로 칠했을 때 최소비용으로 색칠했을 때의 최소비용을 구하는 문제이다.

 

 이 문제는 얼핏보면 모든 경우의 수를 구해서 최솟값을 구하는것 같다만 경우의 수만 3x2의 n승인지라 시간을 무조건 초과하게 되어있다. 이 때 우리는 여기서 다이나믹프로그래밍을 이용하여, 시간을 초과하지 않을 수 있다. 

 필자는 다이나믹 프로그래밍으로 풀겠다는 느낌은 일종의 매트릭스를 만들어 기록하며 훑으며 처리할 수 있고, 이 처리라는 것이 모든 인덱스에서 똑같이 시행되겠다 싶으면 난다. 

 이 문제에서는 집들이 일종의 매트릭스로 나타낼 수도 있다. 예를 들어 2번 집을 초록색으로 칠하고 싶다면 1번 집은 빨간색이거나 파란색일 것이다. 2번 집이 빨간색 일때 최소 비용은 1번 집의 빨or파 비용 중 최소일 것이다. 그렇다면 만약 N번 집이 초록색이라면 N-1번 집이 빨or파 일것이다. 이런 식으로 내가 칠하고 싶은 색을 정해놓고 그 전의 집의 색깔을 정해놓는 느낌으로 코드를 짰다.

 

import sys
input = sys.stdin.readline

def finding_RGB(RGB):
    matrix = [[0,0,0] for _ in range(N)]
    for idx in range(N):
        matrix[idx][0] = min(matrix[idx-1][1],matrix[idx-1][2]) + RGB[idx][0]
        matrix[idx][1] = min(matrix[idx-1][0],matrix[idx-1][2]) + RGB[idx][1]
        matrix[idx][2] = min(matrix[idx-1][0],matrix[idx-1][1]) + RGB[idx][2]

    return min(matrix[N-1])



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

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

print(finding_RGB(RGB))