[17404] RGB거리 2

문제

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

풀이

dp[i]의 i는 첫 번째 집을 i로 색칠 했을 경우를 의미합니다. 0, 1, 2를 빨강, 초록, 파랑으로 생각하면됩니다.

dp[i][j][k]의 i는 i 번째 집을 k 색으로 칠했을 때 0~i 번 집까지의 최소 비용을 의미합니다.

최소 비용을 갱신할 때는 현재 칠할 집을 n이라 했을 때 (n - 1)번 집이 다른 색깔을 칠한 두 가지 경우에서 가장 작은 비용과 현재 집을 색칠할 비용을 더해서 구할 수 있습니다.

위의 과정을 첫 번째 집을 서로 다른 색깔로 칠한 세 가지 경우에서 두 번째 집부터 마지막 집까지 순서대로 최소 비용을 갱신해줍니다.

세 가지의 경우에서 마지막 집까지의 최소 비용 중에서 첫 번째 집을 칠한 색깔을 제외한 두 가지 비용 중 가장 작은 비용을 찾아주고, 이렇게 구한 세 가지의 최소 비용 중 가장 작은 값을 출력하면 됩니다

import sys

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

dp = [[[costs[0][0], sys.maxsize, sys.maxsize]] + [costs[i].copy() for i in range(1, N)],
      [[sys.maxsize, costs[0][1], sys.maxsize]] + [costs[i].copy() for i in range(1, N)],
      [[sys.maxsize, sys.maxsize, costs[0][2]]] + [costs[i].copy() for i in range(1, N)]]

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

dp[0][N-1][0] = dp[1][N-1][1] = dp[2][N-1][2] = sys.maxsize
result1, result2, result3 = min(dp[0][N-1]), min(dp[1][N-1]), min(dp[2][N-1])
print(min(result1, result2, result3))