[BOJ] RGB거리 2

---

코드

import sys
input = sys.stdin.readline

INF = 10e9
n = int(input())
rgb = [list(map(int, input().split())) for _ in range(n)]
ans = INF

for i in range(3):
    dp = [[INF, INF, INF] for _ in range(n)]
    # 1번 집의 색을 먼저 칠한다
    dp[0][i] = rgb[0][i]
    # i(2 ≤ i ≤ N-1)번 집의 색이 i-1, i+1번 집의 색과 같지 않게 한다
    for j in range(1, n):
        dp[j][0] = rgb[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = rgb[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = rgb[j][2] + min(dp[j-1][0], dp[j-1][1])
    # n번 집까지의 최소비용을 구하되 1번 집의 색과 같은 색 인덱스는 제외한다
    for j in range(3):
        if i != j:
            ans = min(ans, dp[-1][j])
print(ans)

결과

풀이 방법

• 1번 집의 색과 N번 집의 색이 달라야 하므로 먼저 1번 집 색깔을 정해놓고 색을 칠해 나갔다
• 2~N번 집의 색은 현재 집을 0~2번 색으로 칠할 때 각각 이전 집에서 선택할 수 있는 색 중 최소값을 취하며 dp배열을 채운다
• 마지막으로, n번 집까지의 최소비용을 구해야 하는데 이때 1번 집의 색과 같은 색의 인덱스는 제외하고 판단한다

---