백준 1932 RGB 거리

문제.

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

풀이.

반복문에서 매 단계 최솟값만을 찾아서 더하면 안되고

조건을 만족하면서 최솟값을 찾아야한다.

R에서 출발하는 최솟값, G에서 출발하는 최솟값, B에서 출발하는 최솟값의 경우를 찾아

마지막에 최솟값을 출력을 한다.

 

소스코드

n = int(input())

cost = [[0 for i in range(3)] for j in range(n)]
color_cost = []
for i in range(n):
    color = list(map(int, input().split()))
    color_cost.append(color)

cost[0] = color_cost[0]

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

print(min(cost[-1]))