17404번 - RGB거리 2 / gold 4 / DP

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

17404번: RGB거리 2

'''
17404번 - RGB거리 2 / gold 4 / DP
'''
import sys

input = sys.stdin.readline
INF = int(1e9)

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

min_value = INF
# 첫 인덱스에서 R,G,B 선택
for i in range(3):
    dp = [[INF, INF, INF] for _ in range(n)]
    dp[0][i] = arr[0][i]
    # dp 알고리즘
    for j in range(1, n):
        dp[j][0] = min(dp[j - 1][1], dp[j - 1][2]) + arr[j][0]
        dp[j][1] = min(dp[j - 1][0], dp[j - 1][2]) + arr[j][1]
        dp[j][2] = min(dp[j - 1][0], dp[j - 1][1]) + arr[j][2]
    # 처음 선택한 i와 다른 인덱스 중 최소값 갱신
    for index in range(3):
        if index != i:
            min_value = min(min_value, dp[n - 1][index])

print(min_value)

 

•  첫 인덱스 R,G,B 선택 
  
  • i = 0이면, 첫번째 집을 R로 선택한 것
  • dp 리스트를 arr 안의 인덱스와 같게 만들고, 최댓값을 넣어둔다.
  • dp[0][i] = arr[0][i]로 갱신 하기
    • 예제 1) dp =[[26, INF, INF] [INF,INF,INF] [INF,INF,INF]] 
• DP 알고리즘 실행
  • dp의 전 인덱스의 다른 색깔 두 가지 경우 중 최솟값 + arr의 현재 인덱스 위치에 있는 값
  •  예제 1) dp = [[26, INF, INF], [INF, 86, 83], [96, 172, 185]]
• 처음 선택한 i 를 제외한 나머지 인덱스 중 최소값 갱신
  • dp[n-1] =[96, 172, 185] 이고, i=0 이므로 빨강 인덱스 제외 중 가장 작은 수 선택 
  • min_value = 172