알고리즘: 백준 1149번 RGB거리 (feat. Python)

 

최적 부분구조와 중복되는 부분이 있으므로 다이나믹 프로그래밍으로 풀어줍니다.

 

 

점화식:

 

 

1. n번째 집에서 R을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 G을 칠할 때 비용의 최솟값, n - 1 번째 집에서 B을 칠할 때 비용의 최솟값 ) + n 번째 R을 칠하는데 드는 비용

 

 

2. n번째 집에서 G을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 R을 칠할 때 비용의 최솟값, n - 1 번째 집에서 B을 칠할 때 비용의 최솟값 ) + n 번째 G을 칠하는데 드는 비용

 

 

3. n번째 집에서 B을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 R을 칠할 때 비용의 최솟값, n - 1 번째 집에서 G을 칠할 때 비용의 최솟값 ) + n 번째 B을 칠하는데 드는 비용

 

 

 

n개의 집을 칠하는 비용의 최솟 값 = min(n번째 집에서 R을 칠할 때 비용의 최솟값, n번째 집에서 G을 칠할 때 비용의 최솟값, n번째 집에서 B을 칠할 때 비용의 최솟값)

 

 

import sys

input = sys.stdin.readline  # 일반 input() 보다 가볍고 빠르다

n = int(input())

array = [[0 for _ in range(3)] for __ in range(n)]  # 3xn 배열
table = [[0 for _ in range(3)] for __ in range(n)]  # 3xn 배열


for i in range(n):
    array[i][0], array[i][1], array[i][2] = list(map(int, input().split()))
    # map을 통해 받아온 인풋 값을 int형으로  



table[0] = array[0]

for i in range(n):

    table[i][0] = min(table[i - 1][1], table[i - 1][2]) + array[i][0]
    table[i][1] = min(table[i - 1][0], table[i - 1][2]) + array[i][1]
    table[i][2] = min(table[i - 1][0], table[i - 1][1]) + array[i][2]


min_cost = min(table[n - 1][0], table[n - 1][1], table[n - 1][2])

print(min_cost)

 

3
26 40 80
49 60 57
13 89 99

96