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

[문제 출처] 

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

1149번: RGB거리

 

 

[문제 풀이]

 

i번째 집을 R, G, B 각 색으로 칠했을 때 비용을 저장하고 n번째 집은 n-1번째 집과 색이 다르다고 했으므로

n번째 집을 x라는 색으로 칠했을 때 n-1번째 집은 x가 아닌 다른 두 색으로 칠할 수 있다.

이점을 이용하여 각 경우에 대하여(R,G,B로 칠한 경우) 최소가 되는 비용을 저장한다.

 

어려운 문제는 아니었으나 문제를 문제 그대로 받아들이지 못해서 헤매고 다른 사람의 풀이를 참고했다.

문제의 핵심을 파악하여 간단하게 생각하는 연습이 필요할 것 같다.

import sys
input = sys.stdin.readline

n = int(input())

cost = []
for _ in range(n):
    r, g, b = map(int, input().split())
    cost.append([r,g,b])

for i in range(1,n):
	#i번째를 빨간색으로 칠했을 때 최소 비용
    cost[i][0] += min(cost[i-1][1], cost[i-1][2])
    #i번째를 초록색으로 칠했을 때 최소 비용
    cost[i][1] += min(cost[i-1][0], cost[i-1][2])
 	#i번째를 파란색으로 칠했을 때 최소 비용
 	cost[i][2] += min(cost[i-1][0], cost[i-1][1])

#마지막 집을 빨, 초, 파 각각 칠했을 때의 최소 비용을 모두 구하고 그 중에서 가장 최소가 되는 값으로 출력
print(min(cost[n-1]))