[백준 1149] RGB 거리 - Python (다이나믹 프로그래밍)

 

1149번: RGB거리

 

<내 코드>

n = int(input())
costs = [0 for _ in range(n+1)]
for i in range(1, n+1):
    costs[i] = list(map(int, input().split()))

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

처음에 생각했을 때는 맨 처음 요소에서 최솟값을 구하면 최소가 되는 줄 알았는데, 그게 아니고 어떤 값을 선택했을 때 최소가 될지는 다 따져줘야 하는 문제였다. 다른 사람의 풀이를 참고하기 전까지는 쓸데없이 어렵게 풀고 헤맸다...

 

1. 첫 요소는 고정이므로 인덱스를 2번째부터 돌리면 된다. 

2. 현재 인덱스 요소의 값과 앞 요소에서 같은 색을 제외한 2가지 중에 최소를 더해준다.

3. 같은 방식으로 마지막까지 3가지 색에 대해 계산을 한다.

4. 마지막 요소의 3가지 값 중 최솟값을 선택하면 최소 비용값을 구할 수 있다.