[백준] Python [1149] RGB거리

 

 

문제

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가지가 있습니다.

 

1. N번째 집은 N-1번째 집과 색깔이 같지 않아야 한다.

2. 가장 저렴한 비용이 들어야 한다.

 

2번째 조건만 있다면 가장 저렴한 가격만 더해주면 해결되지만 1번 조건 때문에 일치하지 않는 경우가 생깁니다.

그래서 N번째 빨강, 초록, 파랑으로 색칠한 경우 3가지를 전부 계산합니다. 예제 1번을 이미지로 표현해 그림 1로 그려 보겠습니다.

그림 1

2번째를 N번째라고 기준을 잡고 설명하겠습니다. N번째를 빨간색으로 칠한 경우를 그림 2로 표현해 봤습니다.

그림2

2번째에서 빨간색으로 칠한 경우는 1(N-1) 번째의 초록색과 파란색 중에서 작은 값을 더해주면 됩니다. 마찬가지로 초록색과 파란색도 값을 구해보겠습니다.

그림 3

 

다음 3(N+1) 번째의 최소 값도 구해보겠습니다.

마지막 번째의 최솟값을 구해주면 정답을 구할 수 있습니다.

 

코드

import sys

n = int(sys.stdin.readline())
h = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
for i in range(1, len(h)):
    h[i][0] += min(h[i - 1][1], h[i - 1][2])
    h[i][1] += min(h[i - 1][0], h[i - 1][2])
    h[i][2] += min(h[i - 1][0], h[i - 1][1])
print(min(h[n - 1][0], h[n - 1][1], h[n - 1][2]))