[백준] RGB거리 2(17404번) - 파이썬(Python)

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

17404번: RGB거리 2

 

1. 문제

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

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

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

---

2. 입력

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

---

3. 출력

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

 

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1 

110

예제 입력 2 

3
1 100 100
100 1 100
100 100 1

예제 출력 2 

3

예제 입력 3

3
1 100 100
100 100 100
1 100 100

예제 출력 3 

201

예제 입력 4 

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4 

 

208

예제 입력 5 

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

예제 출력 5 

253

---

4. 풀이과정

내 풀이

RGB거리(1149번)와 유사한 문제이다. 다른 점이 있다면 기존 문제는 1번과 n번 집의 색을 고려할 필요가 없었지만 이번 문제는 그 둘의 색도 같지 않도록 고려해야 한다는 점이다.

 

따라서 1번이 RGB일 때 3가지 케이스로 나누었다. 그 후, R일 때는 1번의 G, B가 선택되면 안되기 때문에 최대비용+1(1001)을 할당하여 주었다. 그리고 마지막 n번째에서 R인 경우에는 R을 제외한 값중 최소값을 받아서 답을 갱신했고 이를 R,G,B에 각각 3번 반복하여 답을 내었다.

import copy
import sys

input = sys.stdin.readline

n = int(input())

answer = 1e9

arr_or = []
for _ in range(n):
    arr_or.append(list(map(int, input().split())))

# R
arr = copy.deepcopy(arr_or)
arr[0][1], arr[0][2] = 1001, 1001
for i in range(1, n):
    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][0], arr[i-1][2])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])

answer = min(answer, arr[n-1][1], arr[n-1][2])

# G
arr = copy.deepcopy(arr_or)
arr[0][0], arr[0][2] = 1001, 1001
for i in range(1, n):
    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][0], arr[i-1][2])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])

answer = min(answer, arr[n-1][0], arr[n-1][2])

# B
arr = copy.deepcopy(arr_or)
arr[0][0], arr[0][1] = 1001, 1001
for i in range(1, n):
    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][0], arr[i-1][2])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])

answer = min(answer, arr[n-1][0], arr[n-1][1])

print(answer)