문제
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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력
3
26 40 83
49 60 57
13 89 99
예제 출력
96
풀이
1~k번째 집을 칠하려면 먼저 1~k-1번째까지 색을 칠한 후여야 한다. 이후 k번째의 집을 칠할 색을 선택할때 다음과 같이 고려할 수 있다
- 빨간색을 칠할 경우 -> k-1번째 집에서 초록, 파랑색 집이 각각 1~k-1 까지 집을 칠할때 가지는 최소 합계 비용을 비교하여 더 작은 값을 선택
- 초록색을 칠할 경우 -> k-1번째 집에서 빨강, 파랑색 집이 각각 1~k-1까지 집을 칠할때 가지는 최소 합계 비용을 비교하여 더 작은 값을 선택
- 파랑색을 칠할 경우 -> k-1번째 집에서 빨강, 초록색 집이 각각 1~k-1까지 집을 칠할때 가지는 최소 합계 비용을 비교하여 더 작은 값을 선택
주의할 점은, k번째 집을 칠하기 위해서 k-1번째 집의 색칠 비용이 가장 작은 집에서 k번째 집의 선택가능한 최소 비용 색깔을 선택하는게 아니다. 이건 현재에 충실하여 선택하는 그리디 알고리즘이다
예를 들어 4개의 집을 칠한다고 해보자.
(30, 20, 42)
(13, 5, 9)
(25, 32, 64)
(2, 56, 72)
그리디 알고리즘으로 접근하면 결과값은 20-9-25-56 => 110 이다. 그러나 실제 정답은 29-13-32-2 => 67이다.
전체적으로 최적인 선택을 하기 위해선, k번째 집의 색을 칠하기 위해1~k-1까지 집을 칠하고 k-1번째 집을 3개의 색깔로 칠했을때 가질 수 있는 각각의 최소값을 알고 있어야 한다. 그래야 k번째 집을 칠할 때 선택지를 비교하여 항상 최소의 합계를 유지할 수 있다.
dp의 접근 방식
k번째 집의 각각의 색깔을 칠할때 고려한 1~k-1까지의 집을 칠했을때 k-1번째 집의 색깔별로 가질 수 있는 1~k-1까지의 색칠의 최소비용합계는 k+1번째 집을 칠할때도 변하지 않는다. 따라서 부분 최적이 전체의 최적을 만족하는 최적 부분 구조를 만족한다. 그리고 k-1까지의 색칠의 최소 비용합계는 k+1번째 집을 칠할때도 재사용되었으므로 겹치는 부분 문제를 만족한다.
n = int(input())
arr = []
for _ in range(n):
arr.append(list(map(int,input().split())))
# # DP 이용
res = arr[0]
for i in range(1, n):
arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + arr[i][0]
arr[i][1] = min(arr[i-1][0], arr[i-1][2]) + arr[i][1]
arr[i][2] = min(arr[i-1][0], arr[i-1][1]) + arr[i][2]
print(min(arr[n-1]))생각할 점
그리디 알고리즘은 결과값 재사용이 되지 않는다. 그러나 dp의 경우 재사용을 하고, 최적 부분 구조를 만족한다. 방향을 생각해보면 그리디는 값 재사용 없이 단순히 앞만을 보고 향하지만, 그리디는 재사용을 하기 때문에 뒤를 바라보고 이전에 구했던 결과값들을 비교(재사용)하여 최적의 값을 구한다음 앞으로 향한다.
그렇기 때문에 (54,65,97) (2,56,72) 에서 54->110 으로 향하는게 최적이 아니라(이건 그리디 알고리즘), 65 ->2로 향하는게 최적임을 알게 된다. 이전의 집(능동)의 결과를 보고 현재 집(수동)을 선택하는게 아니라 현재 집(능동)에서 이전 집(수동)의 결과를 보고 선택하기 때문이다.
dp로 접근할땐 항상 재사용, 최적 부분 구조를 생각하며 제일 처음 값이 나타내는 의미가 무엇인지 생각하도록 하자.
