백준 1149번_RGB 거리 [ python/파이썬]

 

import sys
 
test_case = int(input())
result_list = [[] for _ in range(test_case)]
for case in range(test_case):
    R, G, B = map(int,sys.stdin.readline().strip().split())
    if case == 0:
        result_list[0].append(R)
        result_list[0].append(G)
        result_list[0].append(B)
    else:
        result_list[case].append(R + min(result_list[case - 1][1], result_list[case - 1][2]))
        result_list[case].append(G + min(result_list[case - 1][0], result_list[case - 1][2]))
        result_list[case].append(B + min(result_list[case - 1][0], result_list[case - 1][1]))
 
print(min(result_list[-1]))

 

# 동적프로그래밍을 하기 위해 n번째의 각 색깔별로 이전까지의 구한 최솟값의 합을 저장한다. 

 

예제를 다음과 같이 정리할 수 있다.

	1번째	2번째	3번째
R	26	49 (89)	13 (96)
G	40	60 (86)	89 (172)
B	83	57 (83)	99 (185)

2번째의 첫 행의 값이 89인 이유는 2번째에 R을 칠할 것이기 때문에 1번째 값으로 R을 선택할 수 없기 때문이다. 따라서 1번째 R이 가장 작은 값이더라도 선택하지 못하므로 G와 B 중 더 작은 G의 40을 선택해야한다. 따라서 40 + 49로 89가 된다. 다른 행도 이와 마찬가지의 규칙을 적용하여 값을 구해주면 된다.