[백준] 17404. RGB거리 2(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 17404. RGB거리 2

시간 제한	메모리 제한	난이도
0.5초	128 MB	골드 4

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

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

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

✔️ 입력

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

✔️ 출력

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

✔️ 입력 출력 예시

입력	출력
3 26 40 83 49 60 57 13 89 99	110
3 1 100 100 100 1 100 100 100 1	3
3 1 100 100 100 100 100 1 100 100	201
6 30 19 5 64 77 64 15 19 97 4 71 57 90 86 84 93 32 91	208
8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19	253

🗒️ 내 풀이

dp[i][k]를 i번 째 집에서 k번 째 색깔(빨강, 초록, 파랑)을 칠했을 때 i번 째 집까지 색깔을 칠한 비용의 최솟값이라고 하자. 이때 첫번째, 두번째 조건을 제외하고 세번째 조건(i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.)만 고려하면, i - 1번 째의 k번 째 색깔을 칠하지 않았을 때의 최솟값에 해당 위치의 색깔 비용을 더하면 최솟값을 얻을 수 있다. 따라서 점화식은 아래와 같다.

\[\begin{align} dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + data[i][0]\\ dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + data[i][1]\\ dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + data[i][2]\\ \end{align}\]

여기서 첫번째, 두번째 조건을 고려해보자. 첫번째 집이 각 빨강, 초록, 파랑을 칠하는 경우를 따로따로 생각해보면 된다. 첫번째 집이 빨강을 칠했다면, n번째 집에서 초록, 파랑을 칠했을 경우 중 최솟값을 구하면 된다. 이렇게 총 3번 해서 최솟값을 구해주면 된다. 따라서 이를 구현하면 아래의 코드와 같다.

import sys
input = sys.stdin.readline
INF = 1e6
n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

result = INF
for k in range(3):
    dp = [[0] * 3 for _ in range(n)]
    
    dp[0][k] = data[0][k]
    dp[0][k - 1] = INF
    dp[0][k - 2] = INF
    for i in range(1, n):
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + data[i][0]
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + data[i][1]
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + data[i][2]
    result = min(result, min(dp[-1][k - 1], dp[-1][k - 2]))

print(result)