[백준 17404번] RGB거리 2 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
INF = sys.maxsize


N = int(input())

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


sol = [[[0]*3 for i in range(N+1)] for i in range(3)]

for i in range(3):
  for j in range(3):
    if i==j:
      sol[i][1][j] = cost[1][i]
    else:
      sol[i][1][j] = INF
for case in range(3):
  s = sol[case]
  for i in range(2,N+1):
    s[i][0] = cost[i][0]+min(s[i-1][1],s[i-1][2])
    s[i][1] = cost[i][1]+min(s[i-1][0],s[i-1][2])
    s[i][2] = cost[i][2]+min(s[i-1][0],s[i-1][1])
  s[N][case] = INF

print(min(min(sol[0][N]),min(sol[1][N]),min(sol[2][N])))

RGB 거리 1 문제에서 살짝 달라진 문제로 DP리스트 3개 만들었던 RGB 1과 다르게 DP리스트를 9개 만들어서 문제를 해결하였다.

 

1번집이 R, G, B인 경우를 나누어서 DP를 3개씩 3번 실행하면 답을 구할 수 있다.

 

 

오늘의 교훈) 음... 열심히 하자