BOJ 1149 RGB 거리

https://www.acmicpc.net/problem/1149
시간 0.5초, 메모리 128MB
input :

• N(2 ≤ N ≤ 1,000)
• 비용(빨강, 초록, 파랑)(1 <= 비용 <= 1000)

output :

• 모든 집을 칠하는 비용의 최솟값을 출력

조건 :

• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

---

현재 색칠하려는 집의 색깔이 이전의 집과 달라야 한다.
그래서 dfs로 하려고 했지만 이 경우엔 시간 복잡도가 초과 된다.

역시 DP와 비슷한 거는 가장 뒤에서 부터 생각하는것이 훨 나은 것 같다.
current_idx에서 prev_idx 값들 중 작은 값을 가져오도록 해서 문제를 해결 할 수 있다.

import sys

n = int(sys.stdin.readline())
data = []
for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    data.append(temp)

for i in range(1, n):
    idx = i - 1
    data[i][0] += min(data[idx][1], data[idx][2])
    data[i][1] += min(data[idx][0], data[idx][2])
    data[i][2] += min(data[idx][0], data[idx][1])

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