백준 1149 RGB거리 (파이썬)

풀이

import sys

N = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]

for i in range(1, N):
    arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + arr[i][0]
    arr[i][1] = min(arr[i-1][0], arr[i-1][2]) + arr[i][1]
    arr[i][2] = min(arr[i-1][1], arr[i-1][0]) + arr[i][2]

rst = 9e9
for j in range(3):
    rst = min(rst, arr[N-1][j])

print(rst)

 

---

후기

• 백트래킹 문제인줄 알고 백트래킹으로 이것 저것 조건 넣어가며 해봤는데, 시간 초과뜸 (30분 정도 날림..)
• 그러다가 알고리즘 분류 보니까 dp라고 나옴...
• dp를 제대로 안배웠지만 간단하게 생각해낼 수 있는 방법이 떠오름

예를 들어, 

[19, 23, 13].

[51, 26, 45].

[84, 44, 31]

 

이렇게 배열이 있으면, 배열의 1번 째 인덱스 [51, 26, 45]에서

51을 기준으로 바로 이전의 인덱스(자신 인덱스 포함x)

즉, 23, 13 중 작은 것을 골라 자신의 값과 더하면, 최소 비용의 총 집 비용이다..

 

반복문 과정에서 51은 51+13이 될것이고, 26은 26+13, 45는 45+19가 되어

[19, 23, 13].

---------------------------

[64, 39, 64].

---------------------------

[84, 44, 31]

 

이렇게 만들어 질 것임, 이 과정을 밑으로 계속 반복해주면 됨

그래서 제일 밑에 만들어진 3개의 값 중 최소 값을 찾아 출력하면 된다.

(dp 배우기 싫다.....)