[골드 4] 백준 17404 - RGB거리 2 (파이썬)

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

풀이

이 문제는 다이나믹 프로그래밍을 사용해서 최소 비용을 계싼하는 문제이다.

각 집은 R(0), G(1), B(2) 중 하나의 색으로만 칠해야 하며, 이웃한 집은 같은 색이면 안된다.

첫번째 집과 마지막 집도 같은 색이면 안된다.

N개의 집이 있고, 각 집의 각 색상별 비용이 주어진다.

즉, 첫번째 집과 마지막 집이 같은색이면 안된다는 조건 때문에 기존 RGB 거리 문제보다 살짝 까다롭다.

그래서 사용한 전략은 다음과 같다.

1. 첫번째 집의 색상을 R, G, B 하나로 고정하고 시작한다. 즉 3가지 경우로 나눠서 각각 따로 계산한다.
2. 그 다음 집부터는 기존 RGB거리처럼 dp[i][j] = i번째 집을 j색으로 칠할 때의 최소 비용을 채워나간다.
3. 마지막 집에서는 첫번째 집과 같은 색이 오지 않도록 확인한다.

예를 들어 집디 3개일때, 다음과 같은 입력이 있다.

26 40 83
49 60 57
13 89 99

각 줄은 각각 집을 빨강, 초록, 파랑으로 칠하는 비용이다.

for first_color in range(3):  # 0(R), 1(G), 2(B)

첫번째 집의 색상을 하나로 고정해서 세번 반복한다.

예를 들면 첫 집을 R로 고정 → G, B로 고정 → …

dp = [[INF]*3 for _ in range(N)]
dp[0][first_color] = A[0][first_color]

DP테이블을 초기화 한다.

첫번째 집은 first_color로 고정해서 그 비용만 기록하고, 나머지 두 색은 절대 고르지 않게 INF로 설정한다.

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

이전 집에서 다른 두 색중 최소 비용을 선택해서, 현재 색을 선택한다.

예를 들어 현재 집을 빨강으로 칠하고 싶으면 이전 집은 초록 / 파랑 중 최소를 택해야 한다.

for last_color in range(3):
    if last_color != first_color:
        answer = min(answer, dp[N-1][last_color])

마지막 집의 색이 첫 집과 같지 않을 때만 답으로 고려하고, dp[N - 1][last_color]은 N - 1번째 집을 특정 색으로 칠한 최소 비용을 나타낸다.

구분 의미

dp[i][j]	i번째 집을 j색으로 칠했을 때의 최소 비용
첫 집 색	세 가지 경우로 나눠서 DP 세 번 돌림
마지막 집 색	첫 집 색과 다를 때만 유효한 정답 후보

코드

# 백준 17404 - RGB거리 2
# 분류 : 다이나믹 프로그래밍

import sys
input = sys.stdin.readline

INF = 1e9

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

answer = INF

for first in range(3) :
    dp = [[INF] * 3 for _ in range(N)]

    dp[0][first] = A[0][first]

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

    for last in range(3) :
        if last != first :
            answer = min(answer, dp[N - 1][last])

print(answer)