백준 1149 RGB거리

Intro

Solution

주어진 규칙 중 세 번째 규칙이 앞의 두 규칙을 모두 포함하는 말이다.

연속으로 같은 색깔을 색깔을 선택할 수 없으므로, 색깔별로 나누어 누적 비용을 저장한다.

n번째 집에서 빨강을 선택할 때는 n-1번째 집에서 초록을 선택할 경우의 비용의 누적 합과 파랑을 선택할 경우의 비용의 누적 합을 비교하여 최솟값을 찾아 더하면 된다.

예를 들어 입력이 다음과 같다고 해보자.

입력
3
26 40 83
49 60 57
13 89 99

그러면 비용의 누적 합은 다음과 같은 순서로 저장된다.

1) dp[1] = [26, 40, 83]

2) dp[2] = [49+min(40, 83), 60+min(26, 83), 57+min(26, 40)]
		 = [89, 86, 83]
         
3) dp[3] = [13+min(86, 83), 89+min(89, 83), 99+min(89, 86)
		 = [96, 172, 185]

Code

import sys; input = sys.stdin.readline

def solve():
	n = int(input())
	dp = [[0]*3 for _ in range(n+1)]
	for i in range(1, n+1):
		dp[i] = list(map(int, input().split()))

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

solve()