파이썬 백준 1149번: RGB거리

문제

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

1149번: RGB거리

 

 

풀이

cost현재까지의 cost를 저장할 리스트를 만들고  R,G,B를 칠하는데 드는 비용을 저장한다.

cost의 해당값은 이전의 값에 해당값을 더하는 방식으로 업데이트 한다.

(업데이트시, 인접한곳은 같은 색으로 칠하지 못하게 하며, 값이 최소인 경우에만 업데이트한다.)

 

예제 1번의 두번째열(49,60,57)의 값 변화는 아래와 같다

실제로 더 큰 값으로 dp테이블이 업데이트 되지 않는다. 이해를 위해 ()안에 계산된 숫자를 넣었다.

노란: 업데이트 대상, 빨강: 비교대상이다.  오른쪽 두 표의 값을 비교하여 작은 쪽이 선택된다.

import sys

N=int(sys.stdin.readline())
cost=[] #비용을 저장할 리스트 
for i in range(N):
    R,G,B=map(int,sys.stdin.readline().split(' '))
    cost.append([R,G,B])

for n in range(1,N): # cost업데이트
    cost[n][0] = min(cost[n-1][1]+cost[n][0],cost[n-1][2]+cost[n][0])
    cost[n][1] = min(cost[n - 1][0]+cost[n][1] , cost[n - 1][2]+cost[n][1] )
    cost[n][2] = min(cost[n - 1][0]+cost[n][2] , cost[n - 1][1]+cost[n][2] )

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