RGB거리[백준 1149] - python

 

정답 코드 먼저 살펴보자

n = int(input())
cost = []
for _ in range(n) :
  cost.append(list(map(int, input().split())))

for i in range(1, len(cost)) :
  cost[i][0] = min(cost[i-1][1], cost[i-1][2]) + cost[i][0]
  cost[i][1] = min(cost[i-1][0], cost[i-1][2]) + cost[i][1]
  cost[i][2] = min(cost[i-1][0], cost[i-1][1]) + cost[i][2]

print(min(cost[n-1][0], cost[n-1][1], cost[n-1][2]))

 

너무 어렵게 생각했었다.

각 라운드에 빨강, 파랑, 초록을 색칠하는 경우를 모두 접근하고 

마지막 라운드에서 그중 최솟값을 선택해서 출력해주자.

 

같은 색깔을 연속해서 칠할수는 없으므로 

빨간색을 칠할때는 그 전 라운드에 초록색을 칠할때와 파란색을 칠할때의 최솟값과 현재 빨간색의 비용을 더해주면 

현재 빨간색을 칠할때의 최소 비용이 구해진다.

 

 

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

1149번: RGB거리