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

1149번: RGB 거리 (실버1)

문제 접근

• 각 집을 빨강(R), 초록(G), 파랑(B) 중 하나로 칠할 수 있음.
• 조건: 인접한 집은 같은 색으로 칠할 수 없음
• 목표: 1번 집부터 N번 집까지 칠할 때, 전체 비용의 최소값을 구하라.

핵심 아이디어

• DP[i][j] = i번째 집을 j색으로 칠할 때의 최소 누적 비용
• 각 i에 대해:
  • DP[i][0] = min(DP[i-1][1], DP[i-1][2]) + cost[i][0] (i번째 집을 빨간색으로 칠함)
  • 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] (파랑)

해답 및 풀이

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][1] += min(cost[i-1][0], cost[i-1][2])  # 초록
    cost[i][2] += min(cost[i-1][0], cost[i-1][1])  # 파랑

print(min(cost[n-1]))  # 마지막 집에서 최소값 출력