백준 1149. RGB거리

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

1149번: RGB거리

'''
인접한 집들의 색이 같지 않아야 함
R,G,B 세 가지 색으로 칠함

i번째 집을 칠하는 비용은 i-1번째 집에 따라 달라짐
dp[i][color]를 i번째 집까지 칠하는 데 드는 최소 비용으로 설정
'''

import sys
input = sys.stdin.readline

N = int(input())
cost = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0] = cost[0] # 첫 번째 집을 칠하는 비용은 그대로(시작이니까)

for i in range(1,N):
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]  # 빨강으로 칠하는 최소 비용
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]  # 초록으로 칠하는 최소 비용
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]  # 파랑으로 칠하는 최소 비용

print(min(dp[N-1]))

'''
이렇게 dp를 따로 안만들고 갱신해나가는 방법도 있음! 메모리 차이는 없고 시간 차이 조금 남!
import sys
input = sys.stdin.readline

N = int(input())
cost = [list(map(int, input().split())) for _ in range(N)]
    
for i in range(1,n):
    cost[i][0]= min(cost[i-1][1],cost[i-1][2]) + cost[i][0]
    cost[i][1]= min(cost[i-1][0],cost[i-1][2]) + cost[i][1]
    cost[i][2]= min(cost[i-1][0],cost[i-1][1]) + cost[i][2]

print(min(cost[n-1][0],cost[n-1][1],cost[n-1][2]))
'''

+ 24.10.24

n = int(input())

# 인접한 하나 or 두개의 집과 색이 같으면 안됨!

graph = [list(map(int,input().split())) for _ in range(n)]
dp = [[0 for _ in range(3)] for _ in range(n)]

for k in range(3): # 초기값 세팅
    dp[0][k] = graph[0][k]

# 1번째 집부터 n-1번째 집까지의 최소 비용을 구함
for i in range(1, n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + graph[i][0]  # R을 선택한 경우
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + graph[i][1]  # G를 선택한 경우
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + graph[i][2]  # B를 선택한 경우

print(min(dp[-1]))