[백준] 1149: RGB거리 (Python)

1149: RGB거리

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

1149번: RGB거리

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이

연속해서 같은 색상으로 집을 칠할 수 없으므로 직전에 어떤 색상으로 집을 칠했는지를 고려해야 한다. 따라서 dp 테이블을 n*3 2차원 리스트로 만들어 해결했다. 하나의 집을 3가지 색으로 칠하는데 드는 비용이 한 줄에 하나씩 입력되므로 cost도 n*3 2차원 리스트로 만들었다. dp[i][0]을 i번째 집에 빨간색을 칠하는 경우의 최소 비용, dp[i][1]을 i번째 집에 초록색을 칠하는 경우의 최소 비용, dp[i][2]를 i번째 집에 파란색을 칠하는 경우의 최소 비용으로 보았다.

 

점화식은 다음과 같은 형태다.

i번째 집에 A색을 칠하는 경우의 최소 비용 = min(i-1번째 집에 B색을 칠하는 경우의 최소 비용, i-1번째 집에 C색을 칠하는 경우의 최소 비용) + i번째 집에 A색을 칠하는 데 드는 비용

즉 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0] 이다.

# 1149: 401 - 다이나믹 프로그래밍 1 연습 - RGB거리
n = int(input())
cost = []
for i in range(n):
    cost.append(list(map(int, input().split())))
dp = [[0]*3 for i in range(n)]
for i in range(3):
    dp[0][i] = cost[0][i]
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]))