[백준] 1149 RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

N = int(input())
total = [[0]*3 for _ in range(N + 1)]

for i in range(1, N + 1):
    x, y, z = list(map(int, input().split()))
    if i == 1:
        total[i] = [x, y, z]
    else:
        total[i][0] = min(total[i - 1][1], total[i - 1][2]) + x
        total[i][1] = min(total[i - 1][0], total[i - 1][2]) + y
        total[i][2] = min(total[i - 1][1], total[i - 1][0]) + z
print(min(total[N]))

대충 백트래킹으로 조합을짜면 할수있었는데 DP로 하려니 어떻게 해야하는지 감이 안잡혔다.

처음엔 값을 받아서 이전 자리와 다른인덱스 값중 최솟값을 넣는 식으로 짰는데, 틀린 답이 나왔다.

한시간 정도 고민했는데 안풀려서 자야하기때문에 검색해보았다.

이방식으로하면 index에는 각각 x,y,z와 이전 row값에서 가장 작은 값을 더해서 저장하게 된다.

번거롭게 index를 체크하지 않아도 되니 참으로 좋은 방법인듯하다.