문제 설명

구현 아이디어

1번 집부터 시작하여 N번 집까지 차례로 집을 칠한다.

• K번 집을 R로 최소 비용 = (K-1)을 G 또는 B로 칠했을 때 총 비용 중 작은 것 + K번 집을 R로 칠하는 비용
• K번 집을 G로 최소 비용 = (K-1)을 R 또는 B로 칠했을 때 총 비용 중 작은 것 + K번 집을 R로 칠하는 비용
• K번 집을 B로 최소 비용 = (K-1)을 R 또는 G로 칠했을 때 총 비용 중 작은 것 + K번 집을 R로 칠하는 비용

예제 1을 예시로 들어보자.

1. 1번 집을 먼저 칠한다

	R	G	B
1번 🏠	26	40	83
2번 🏠
3번 🏠

2. 1번 집에 칠하지 않은 색 중 하나를 골라 2번 집을 칠한다.

	R	G	B
1번 🏠	26	40	83
2번 🏠	49 + min(40, 83)	60 + min(26, 83)	57 + min(26, 40)
3번 🏠

3. 2번 집에 칠하지 않은 색 중 하나를 골라 3번 집을 칠한다.

	R	G	B
1번 🏠	26	40	83
2번 🏠	89	86	83
3번 🏠	13 + min(86, 83)	89 + min(89, 83)	99 + min(89, 86)

min()을 계산하여 표를 다시 정리하면 아래와 같다.

	R	G	B
1번 🏠	26	40	83
2번 🏠	89	86	83
3번 🏠	96	172	185

마지막 집을 각각 R, G, B로 칠했을 때의 비용 중 최소는 96이므로, 정답은 96이 된다.

전체 코드

import sys

input = sys.stdin.readline

n = int(input())

rgb = [] # 각 집을 빨강, 초록, 파랑으로 칠하는 비용
dp = [[0 for _ in range(3)] for _ in range(n)] # 집을 칠하는 누적 비용

for _ in range(n):
    rgb.append(list(map(int, input().split())))

dp[0] = rgb[0]

for i in range(1, n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2])+rgb[i][0] # i번째 집을 R로 칠했을 때 최소 비용
    dp[i][1] = min(dp[i-1][0], dp[i-1][2])+rgb[i][1] # i번째 집을 G로 칠했을 때 최소 비용
    dp[i][2] = min(dp[i-1][0], dp[i-1][1])+rgb[i][2] # i번째 집을 B로 칠했을 때 최소 비용

print(min(dp[n-1])) # 마지막 행에서 가장 작은 값이 최종적인 최소값