[BOJ/1149] RGB 거리 - 풀이 및 코드

문제 설명

과정

 N개의 집이 존재하고 해당 집을 채색하는데 드는 비용이 주어지며, 인접한 집은 세가지 색(R, G, B) 중 서로 다른 색깔로 칠할 때, 모든 집을 칠할 때 드는 비용의 최소값을 출력하면 되는 문제입니다.

 

 처음에는 그리디 알고리즘을 사용해서 풀어도 될 것 같은 생각이 들었지만, 다음과 같은 상황에서는 불가능합니다.
(탐욕법을 이용하여 최소 비용을 구하려고 하면 아래 사례에선 절대로 최소 비용을 구하지 못합니다)

index: 1  2  3
R:       1  9  1
G:       1 10 100
B:        1 10 100

 현재 "가장 좋은 대안을 선택" 하였을 때 "그 선택으로 인해 추후 더 나은 선택을 할 수 없다." 라는 점 때문에 탐욕법은 사용할 수 없습니다. 그런데 위와 같은 반례를 작성해보며 이전 선택을 "기억하면 문제를 쉽게 풀 수 있음"을 알았습니다. 만약 이전 선택을 기억하지 않으면 모든 사례를 완전 탐색해야 하기 때문에 그 경우 시간 복잡도는 O(2^n)으로 매우 큽니다.

 

 따라서, 이 문제는 동적 계획법으로 해결해야합니다. "이전 선택"을 기억해야 문제를 빨리 풀 수 있으며, 그 "선택"에는 이전에 칠한 색깔과 비용이 포함되어야 합니다. 아래 사례를 보며 생각해보겠습니다.

 

 i번째 집을 칠한다고 가정해봅시다. 만약 i번째 집을 빨간색으로 칠한다면 i-1 번째에 칠한 색은 반드시 초록과 파랑 둘 중 하나일 것입니다. i-1 번째를 초록과 파랑으로 칠하는 최소 비용을 각각 G(i-1), B(i-1)로 정의하면 i번째 집을 칠하는 최소 비용은 다음과 같게 됩니다.

R[i] = min( G[i-1], B[i-1] ) + i번째를 빨간색으로 칠하는 비용
(단, R[i]는 i번째 집을 빨간색으로 칠할 때 드는 최소 비용)

점화식을 위와 같이 세우고 모든 색깔에 대해 DP 테이블을 갱신해주면 되기 때문에 시간복잡도 O(N)내에 문제를 풀 수 있게 됩니다.

코드

코드를 그대로 복사 붙여넣기 하여 제출하는 치팅 행위는 BOJ 정지 사유입니다!

# 집을 입력받으며 색깔을 기록
n = int(input())
# R: 0, G: 1, B: 2
houses = [list(map(int, input().split())) for _ in range(n)]
# DP 테이블 생성
dp = [[0, 0, 0] for _ in range(n)]

# DP[i][0] => i번째 집의 색상을 R로 선택했을 때 최소 비용
# DP[i][0] = min(DP[i][1], DP[i][2]) + houses[i][0]
# 초기 조건 삽입
for i in range(3):
    dp[0][i] = houses[0][i]

# dp 테이블 갱신
# 우선 집을 순회합니다
for i in range(1, n):
    house = houses[i]
    # 이후 비용을 참조하며 dp 테이블을 갱신합니다
    for j in range(3):
        # j번째 색상 외의 색상: c1, c2
        # 0 -> 1, 2 | 1 -> 2, 0 | 2 -> 0, 1
        c1 = (j + 1) % 3
        c2 = (j + 2) % 3
        # R,G,B의 비용
        cost = house[j]
        dp[i][j] = min(dp[i-1][c1], dp[i-1][c2]) + cost

print(min(dp[-1]))

참고자료

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

1149번: RGB거리