BOJ | 17404 - RGB거리 2 (python)

🚥 백준 17404번 RGB거리 2

RGB거리 업그레이드된 문제. 다이나믹 프로그래밍

 

 

---

✏️ 문제

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보다 작거나 같은 자연수이다.

 

출력

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

---

💡 해결방법

백준 1149번 RGB거리 와 비슷한 문제로, 1번집과 n번집의 색깔이 같으면 안된다는 조건이 추가된 문제이다.

1번집과 n번집의 색깔도 같지 않게 해줘야 한다는 것은 1번집의 색깔도 기억해야 한다.

 

그러므로 1번집의 색깔을 지정하고 n번째 집까지의 최소비용을 구하는 것이다.

최솟값을 구해야 하므로 1번집의 색을 지정하고 시작한다면 나머지 집은 무한대의 값으로 지정해주어야 한다.

이후부터는 2번집부터 n번집까지 점화식을 돌려 최솟값을 구해준다.

 

이후에 예를 들어 1번집의 색깔을 지정하고 들어갔다면 마지막에 나온 최솟값(마지막 n번집까지 모두 더한 색깔의 최솟값) 중에서 마지막 1번집 색깔을 고려하면 안되므로 2번집과 3번집 중 최솟값만 고려하면 된다.

 

for 문 안이 돌아가는 것을 보자면 다음과 같다.

i가 0 일때 1번집의 색깔을 지정한다.
이 때, 1번집의 색깔 제외하고 모두 무한대의 값을 지정해준다.
d[0] = [1번집의 R색깔의 비용, INF, INF]
위와 같이 초기화를 시켜준 후 1~N까지 최소비용을 구한다.

예시로 마지막 값이 [10,40,30]이 나왔다면 기본 RGB문제는 10이 정답이지만, 이 문제는 1번집의 색깔과 N번집의 색깔이 같으면 안되므로 R색깔은 무시하고 40과 30을 비교하여 최솟값인 30의 수를 answer값으로 구하면 된다.

이런식으로 1번집의 색깔을 G, B 로도 지정해준 후 돌려 answer값을 계속해서 갱신하면 된다.

 

 

👩🏻‍💻 소스코드

# 17404 : RGB거리 2

import sys
input = sys.stdin.readline

N = int(input())
rgb = [list(map(int, input().split())) for _ in range(N)]
d = [[0, 0, 0] for _ in range(2)]
INF = int(1e9)
res = INF


for i in range(3):
    d[0] = [INF, INF, INF]
    d[0][i] = rgb[0][i]

    for j in range(1, N):
        d[1][0] = min(d[0][1], d[0][2]) + rgb[j][0]
        d[1][1] = min(d[0][0], d[0][2]) + rgb[j][1]
        d[1][2] = min(d[0][0], d[0][1]) + rgb[j][2]

        d[0][0], d[0][1], d[0][2] = d[1][0], d[1][1], d[1][2]

    for k in range(3):
        if i != k:
            res = min(d[1][k], res)

print(res)

 

---

 

 

17404번: RGB거리 2