[백준 1149] RGB 거리

문제

RGB 거리에 집이 N개 있다. 집은 1번부터 N번 집이 순서대로 있다.

이때 집의 색은 빨강, 초록, 파랑 중에 하나로 색칠을 해야하는데 옆에 같은 색깔의 집이 있을 수 없다.

N개의 집을 모두 칠하는데 드는 최소비용을 구하라.

 

입력

집의 개수 N이 입력된다. (2이상 1000이하)

이후에 각 번호에서 R, G, B로 색칠할 때 드는 비용이 입력된다.

 

출력

N개의 집을 색칠하는데 드는 최소비용을 출력한다.

---

접근

N개의 집이 있을 때 집이 1개만 있을 때는 어떨지 나눠보았다. 그리디로 접근은 불가능했다. 현재 선택한 최소비용이 나중에  최소가 되지 않을 수 있었기 때문이다. 

모든 경우의 수를 구한다고 했을 때 만약 1번 집을 R로 색칠하면 2번 집은 G, B 중에 하나로 색칠할 수 있는데 G B 중 최소비용을 선택해야한다. 이렇게 2번 집까지 색칠하면 3번 집은 2번집과 다른 색으로 색칠해야하며 역시 최소비용을 선택해야한다. 

 

이렇게 하는 것이 동적계획법인지 아직 확실하진 않다.

2번 집부터 색을 선택할 때 R을 선택하면 1번 집에서 G, B로 색칠이 되어있어야하기 때문에 G B중 최솟값을 R에 더한다. 그리고 G는 1번집이 R과 B가 선택되어 있어야하기 때문에 R과 B 중 최소 비용을 2번의 G에 더한다. 이런식으로 나아가면 마지막 N번째 집에는 지금까지 모두 색을 칠했을 때 나온 비용이 포함되어있을 것이고 이 중에서 최소를 선택한다.

 

구현

집의 개수와 색상 정보를 입력받는다.

N = int(input())
rgb_map = [list(map(int, input().split())) for _ in range(N)]

 

1번 인덱스부터 전의 집과 비교하여 최소비용을 더해나간다.

마지막 N-1집에 모든 비용이 합쳐있으며 그 중 최소비용을 선택하여 출력하도록 한다.

for y in range(1, N):
    rgb_map[y][0] += min(rgb_map[y-1][1], rgb_map[y-1][2])
    rgb_map[y][1] += min(rgb_map[y-1][0], rgb_map[y-1][2])
    rgb_map[y][2] += min(rgb_map[y-1][0], rgb_map[y-1][1])

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
rgb_map = [list(map(int, input().split())) for _ in range(N)]

for y in range(1, N):
    rgb_map[y][0] += min(rgb_map[y-1][1], rgb_map[y-1][2])
    rgb_map[y][1] += min(rgb_map[y-1][0], rgb_map[y-1][2])
    rgb_map[y][2] += min(rgb_map[y-1][0], rgb_map[y-1][1])

answer = min(rgb_map[N-1][0], min(rgb_map[N-1][1], rgb_map[N-1][2]))
print(answer)