[파이썬, Python] 백준 1149: RGB거리

문제

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

1149번: RGB거리

코드

import sys
input = sys.stdin.readline


n = int(input())
dp = list(list(map(int, input().split())) for _ in range(n))

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

설명

처음에 최솟값만 dp 리스트에 넣으려고 하다가 반례를 찾아서 다른 방법을 모색했다.

100 100 1
100 100 100
1 100 100
이런 리스트의 경우 최솟값의 인덱스만 가지고 풀려고 하면 오류가 났다.

따라서 다른 방법을 찾았다.

모든 색에 대한 최솟값을 비교를 해주어야 한다.

2번째 집에 각각 RGB를 칠한다고 가정하고 계산을 해야 한다.
그러려면 그 이전에 색칠한 색의 최솟값을 가져와야 한다.

R을 칠한다고 가정하면 1번째 집의 G, B 중의 최솟값을 가져와서 R의 값과 더해야 한다.
G를 칠한다고 가정하면 1번째 집의 R, B 중의 최솟값을 가져와서 G의 값과 더해야 한다.
B를 칠한다고 가정하면 1번째 집의 R, G 중의 최솟값을 가져와서 B의 값과 더해야 한다.

이렇게 쭉 마지막까지 더했을 때의 최솟값이 정답이 된다.