[🥇4 / 백준 17404 / 파이썬] RGB거리 2

 

17404번: RGB거리 2

 

문제

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

 

풀이

 

[🥈1 / 백준 1149 / 파이썬] RGB거리 (최적 부분구조)

 

위 문제의 업그레이드 버전이다.

이번에는 집이 선형이 아닌 원형 구조로 놓여있기 때문에 마지막 집과 첫 번째 집도 색이 겹치지 말아야 한다.

 

따라서 dp 배열을 3 * 3 크기로 만들어 각각 어느 집부터 시작했는지 표시하고 마지막에 따로 처리해줄 것이다.

우선 예제를 풀 때 맨 처음 dp 배열은 아래와 같다.

 

 

각각 왼쪽부터 처음 집이 R, G, B로 시작하는 경우를 나타낸다.

시작 지점 말고는 무한대인 inf로 처리해야 그 바로 다음 집이 처음 집 말고 다른 집의 가격을 가져와 계산하는 불상사가 없어진다.

 

이제 입력을 받아 최솟값을 갱신해나가며 dp를 n-1 번째 집까지 쭉 진행한다.

마지막이 되었다면 바로 이전 집, 그리고 첫 번째 집의 색상과 겹치지 않게 하여 최솟값을 계산해주면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
start = list(map(int,input().split()))
dp = [[float('inf')]*3 for i in range(3)]
for i in range(3):
    dp[i][i] = start[i]
print(dp)

# 2 ~ n-1 집
for _ in range(n-2):
    r,g,b = map(int,input().split())
    for i in range(3):
        tmp = dp[i][:]
        dp[i][0] = r + min(tmp[1],tmp[2])
        dp[i][1] = g + min(tmp[0],tmp[2])
        dp[i][2] = b + min(tmp[0],tmp[1])

# n 번째 집
ans = [i[:] for i in dp]
if n > 1:
    rgb = list(map(int,input().split()))
    for i in range(3):
        for j in range(3):
            tmp,tmpRgb = dp[i][:],rgb[:]
            tmp[j],tmpRgb[i] = float('inf'),float('inf')
            
            ans[i][j] = tmpRgb[j] + min(tmp)
            
r = float('inf')
for i in ans:
    r = min(*i,r)
print(r)