[python] 백준 1149번 : RGB 거리 (DP)

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

1149번: RGB거리

 

1. 구현

n = int(input())
RGB = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
    RGB[i][0] = min(RGB[i-1][1], RGB[i-1][2]) + RGB[i][0]
    RGB[i][1] = min(RGB[i - 1][0], RGB[i - 1][2]) + RGB[i][1]
    RGB[i][2] = min(RGB[i - 1][1], RGB[i - 1][0]) + RGB[i][2]
print(min(RGB[n-1]))

 

i번째에 Red를 선택할 경우 > i-1번째 Green, Blue 중 비용이 작은 값 

i번째에 Green를 선택할 경우 > i-1번째 Red, Blue 중 비용이 작은 값

i번째에 Blue를 선택할 경우 > i-1번째 Red, Green 중 비용이 작은 값 

 

RGB[i][0] : i번째에 Red를 선택한 경우, i번째까지의 총 비용 저장 

 

예시 1 2 3

       4 4 4

       7 2 9

 

 

1번째 집: 빨강 4를 선택한 경우 2과 3중 최솟값인 2 포함 6 저장   

             그린 4를 선택한 경우 1과 3중 최솟값인 1 포함 5 저장

             블루 4를 선택한 경우 1과 2중 최솟값인 1 포함 5 저장 .

.... 

 

결과 1 2 3

       6 5 5

       12 7 14