[백준] 1149 RGB거리 파이썬 python

문제링크

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

1149번: RGB거리

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
 
d = [list(map(int,input().split())) for _ in range(n)]
 
for i in range(1,n):
    for j in range(3):
        if j ==0:
            d[i][j] = min(d[i-1][1],d[i-1][2])+d[i][j]
        elif j ==1:
            d[i][j] = min(d[i-1][0],d[i-1][2])+d[i][j]
        else:
            d[i][j] = min(d[i-1][0],d[i-1][1])+d[i][j]
 
ans = min(d[n-1][0],d[n-1][1],d[n-1][2])
print(ans)

 

POINT

- DP로 접근

- d[i][j] : i번째 집을 j 색상으로 칠했을 때 총 최소 비용

색상 R,G,B -> j = 0,1,2

연속적으로 색상이 겹치면 안되니 추가적으로 색상 정보도 기록해야한다. 현재 칠할 색상과 다른 색상으로 칠해진 직전 case들 중 더 작은 비용인 case를 선택해가면서 값을 갱신한다. 

 

예를 들어, i번째 집을 0번 색상으로 칠하고자할 때의 최소 비용은

i-1번째 집이 1번 혹은 2번으로 칠해진 case 중 더 적은 비용인 case를 선택하고,
현재 i번째 집 0번색상 페인트값을 더한다. (아래 식에서 색상을 동일시하여 표현)

==> d[i][0] = min( d[i-1][1], d[i-1][2] )+d[i][0]