[백준] 1149번 RGB거리

백준_1149

전형적인 dp문제다
내가 dp를 푸는 방법은 진행 방향을 거꾸로 해서 문제를 생각해본다
문제에서는 위에서 아래로 내려오는 형식이지만, 현재 위치에서의 전 방향, 즉 아래에서 위로 변수를 고려하는 것이다

이를 이 문제에 적용해보면 현재 집에서 색칠할 색(j번)을 정하고, 이전 집에서 다른 색으로 색칠한(j번을 제외한 색들)경우 중에서 비용이 가장 적은 색을 골라 더하는 것이다

dp 테이블을 따로 만들어서 풀어도 되지만, 좀 더 편하게 하기 위해 색칠하는 비용 테이블을 그대로 사용했다

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

for i in range(1,n):
    for j in range(3):
        rgb[i][j] += min(rgb[i-1][:j]+rgb[i-1][j+1:])

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