[백준 1149번] RGB거리

import sys
input = sys.stdin.readline

n = int(input())

area = [[0]*3 for _ in range(n)]
dp = [[0]*3 for _ in range(n)]

for i in range(n):
    area[i] = list(map(int,input().split()))

dp[0] = area[0]

for i in range(1,n):
    for j in range(3):
        if j == 0:
            dp[i][j] = area[i][j] + min(dp[i-1][1], dp[i-1][2])
        elif j == 1:
            dp[i][j] = area[i][j] + min(dp[i-1][0], dp[i-1][2])
        else:
            dp[i][j] = area[i][j] + min(dp[i-1][0], dp[i-1][1])

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

이번 문제는 각 집마다의 RGB 비용들이 주어진 상황에서, 다음과 같은 3가지 조건을 만족하면서 모든 집을 칠하는 비용을 최소화하는 문제이다.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

N번째 집이 N-1번째 집의 색깔이 겹치지 않도록 하면서 최소 값을 찾아가는 방식으로 DP리스트를 채워나가면 어렵지 않게 풀 수 있는 문제였다

 

이번 문제는 반복문을 사용하여 작은 값들부터 DP 리스트에 현재까지의 최소 값을 저장하는 DP 알고리즘을 사용하여서 간단하게 풀이할 수 있었다 :)