1149번: RGB거리

1149번: RGB거리

 

DP 문제다.

1번부터 N번의 집을 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.

그리고 인접한 집의 색은 달라야 한다.

 

즉, i번째 집의 색은 i-1번째 집의 색의 영향을 받아서 정해진다.

i-1번째 집이 빨강일 경우 i번째 집은 초록, 파랑만 가능하다.

i-1번째 집이 초록일 경우 i번째 집은 빨강, 파랑만 가능하다.

i-1번째 집이 파랑일 경우 i번째 집은 빨강, 초록만 가능하다.

 

쉬운 문제인 줄 알았는데 생각보다 까다로웠다.

만약 i번째 집에서 빨강을 골랐을 경우, 최솟값은 i-1번째에서 초록, 파랑을 골랐을 경우의 최솟값 + i번째 집을 빨간색으로 칠하는 비용이다.

만약 i번째 집에서 초록을 골랐을 경우, 최솟값은 i-1번째에서 빨강, 파랑을 골랐을 경우의 최솟값 + i번째 집을 초록색으로 칠하는 비용이다.

만약 i번째 집에서 파랑을 골랐을 경우, 최솟값은 i-1번째에서 빨강, 초록을 골랐을 경우의 최솟값 + i번째 집을 파랑색으로 칠하는 비용이다.

 

각 경우를 모두 구해준 다음, 마지막에 n번째 집에서 빨강, 초록, 파랑을 골랐을 경우 각각에서 최솟값을 구해야 답이 나온다.

그래서 dp테이블을 2차원 배열로 구현해서, i번째 집에서 빨강, 초록, 파랑을 골랐을 때의 최솟값을 나눠서 구해야 한다.

 

# 1149번: RGB거리
n = int(input())

dp = [[0 for _ in range(1001)] for _ in range(1001)]
arr = []

for i in range(n):
    r, g, b = map(int, input().split())
    arr.append((r, g, b))


for i in range(n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2]

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