파이썬 RGB 거리(백준 BOJ 1149)

문제

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

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

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

입력

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

출력

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

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

96

예제 입력 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

102

예제 입력 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

📝 풀어보기

📌 N개의 집을 입력받는다. 빨강, 파랑, 초록 3가지의 집을 칠하는 비용을 담기 위한 리스트를 생성한다.

N만큼 반복하면서 빨강, 파랑, 초록 순으로 집을 칠하는 비용을 리스트의 형태로 입력받는다. 입력을 받으면 리스트에는 다음과 같이 값이 들어갈것이다. RGB = [[26, 40, 83]]

import sys
N = int(input())
RGB = []

for i in range(N):
    RGB.append(list(map(int, input().split())))
    # RGB = [[26, 40, 83]]

📌 1부터 리스트 RGB의 길이까지 반복하면서 0번째 인덱스의 요소 다음 값부터

첫번째(R)에는 RGB[i][0] 의 원래 값에 RGB[i-1][1](G), ` RGB[i-1][2]`(B)를 칠하는 것 중 더 비용이 적게 드는 값을 누적시킨다.

두번째(G)에는 RGB[i][1]의 원래 값에 RGB[i-1][0](R), RGB[i-1][2](B)를 칠하는 것 중 더 비용이 적게 드는 값을 누적시킨다.

세번째(B)에는 RGB[i][2]의 원래 값에 RGB[i-1][0](R), RGB[i-1][1](G)를 칠하는 것 중 더 비용이 적게 드는 값을 누적시킨다.

이렇게 계산하는 이유는

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

세 가지 조건이 있기 때문이다.

마지막으로 리스트 요소의 맨 끝 RGB[N-1] 에 누적된 R,G,B의 누적 값 중 가장 작은 값을 가져오면 최소비용을 출력할 수 있다.

for i in range(1, len(RGB)):
    RGB[i][0] += min(RGB[i-1][1], RGB[i-1][2]) # [0][1], [0][2] 중 최소값 누적
    RGB[i][1] += min(RGB[i-1][0], RGB[i-1][2])
    RGB[i][2] += min(RGB[i-1][0], RGB[i-1][1])
print(min(RGB[N-1][0], RGB[N-1][1], RGB[N-1][2]))

전체 코드

# 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
# N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
# i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
import sys
N = int(input())
RGB = []

for i in range(N):
    RGB.append(list(map(int, input().split())))
    # RGB = [[26, 40, 83]]

for i in range(1, len(RGB)):
    RGB[i][0] += min(RGB[i-1][1], RGB[i-1][2]) # [0][1], [0][2] 중 최소값 누적
    RGB[i][1] += min(RGB[i-1][0], RGB[i-1][2])
    RGB[i][2] += min(RGB[i-1][0], RGB[i-1][1])
print(min(RGB[N-1][0], RGB[N-1][1], RGB[N-1][2]))