[백준/파이썬] 1149 RGB거리

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

---

알고리즘 분류

• 다이나믹 프로그래밍

문제풀이

처음에 0번 집에서 최소값을 가지는 색깔을 선택해서 풀었는데
다음과 같은 반례 때문에 실패했다.
ex)
2
100 1 100
999 1 999 -> 101이 나와야함


1번 집에서 R를 선택했을 경우 0번 집은 G,B중에서 최소값을 선택했을 것이다. 그 값과 원래 값을 계속해서 합산해나간다.
1번 집에서 G를 선택했을 경우 0번 집은 R,B중에서 최소값 선택...

ex)
49=min(40,83)+49=89
60=min(26,83)+60=86
57=min(26,40)+57=83

26 40 83
49 60 57
13 89 99
↓
26 40 83
89 86 83
13 89 99

소스코드

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

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

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

참고: https://pacific-ocean.tistory.com/147