[백준] 1149번 RGB거리 (Python)

문제

 

www.acmicpc.net/problem/1149

1149번: RGB거리

 

코드

T = int(input())
rgb = []

for i in range(T):
    rgb.append(list(map(int,(input().split()))))


for i in range(1,T):
    rgb[i][0] = rgb[i][0] + min(rgb[i-1][1], rgb[i-1][2])
    rgb[i][1] = rgb[i][1] + min(rgb[i-1][0], rgb[i-1][2])
    rgb[i][2] = rgb[i][2] + min(rgb[i-1][0], rgb[i-1][1])


print(min(rgb[T-1]))

# rgb (입력)
# 26 40 83
# 49 60 57
# 13 89 99

# rgb 
# 26 40 83
# 89 86 83
# 96 172 185

 

코드설명

최적의 해를 찾기위해서 이전에 값에서 자신의 색깔을 제외한 두 색깔중 작은 값과 더해간다.

dp를 이용해 값을 저장해주고 그 값중 가장 작은 값을 출력해주면 된다.

 

rgb 이중배열에서 rgb[1]부터 [T-1]까지 for문을 돌린다. rgb[0]에는 원래 입력값이 들어있어 그값을 토대로 [T-1]까지 더해가면 된다.

 

rgb[T-1]중에서 가장 작은 값을 출력하면 그 값이 최솟값이다.