[Python] 백준 1149번 - RGB 거리

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

1149번: RGB거리

 

아 디피 어렵다!!!!!!!

 

어떻게 풀어야 하나 감이 안 잡혔는데 시간제한이 0.5초라서 이중 for문은 절대 쓰면 안 됐고,,

혹시 DP인가... 하면서 알고리즘 분류를 확인했더니 DP가 맞았다.

 

처음에 for문을 0번 인덱스부터 돌려서 좀 헤맸다.

1번 인덱스부터 돌리면 바로 전 집의 최솟값과 자신의 값을 더해서 값을 갱신해주면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]

for i in range(1, n):
    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]) #초록
    cost[i][2] += min(cost[i-1][0], cost[i-1][1]) #파랑

print(min(cost[-1]))