[동적계획법, 난이도 중] 백준 1149번 RGB거리

집에 색을 칠하는 조건 3가지가 명시되어있다.

 

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

간단하게 요약하자면 인접한 집끼리는 다른 색이어야 한다는 것이다.

 

 

즉 n번째 집까지 칠했을 때 n번째 집이 R이라면 비용의 최솟값은 n-1번째 집이 G색일경우의 총 비용의 최솟값과 n-1번째 집이 B색일경우의 총 비용의 최솟값중 더 작은 값.

그리고 n번째 집까지 칠했을 때 n번째 집이 G이라면 비용의 최솟값은 n-1번째 집이 R색일경우의 총 비용의 최솟값과 n-1번째 집이 B색일경우의 총 비용의 최솟값중 더 작은 값.

그리고 n번째 집까지 칠했을 때 n번째 집이 B이라면 비용의 최솟값은 n-1번째 집이 R색일경우의 총 비용의 최솟값과 n-1번째 집이 G색일경우의 총 비용의 최솟값중 더 작은 값.

 

이 규칙에 대해 DP를 수행하면 된다.

 

문장이 길었는데 예제 1의 입력에 대해 수행할 때 DP표로 간단히 요약하면 이렇다.

<입력>

3

26 40 83

49 60 57

13 89 99

 

<식>

<값>

 

n번째 집까지 모두 칠했을 때의 비용의 경우는 (96,172,185) 가 되는데 이 비용들의 최솟값인 96가 예제의 답이 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int e[1001][3];
int n;

int main() {
	cin>>n;
	for(int i=0;i<n;i++)for(int j=0;j<3;j++)cin>>e[i][j];
	for(int i=1;i<n;i++){
		e[i][0]+=min(e[i-1][1],e[i-1][2]);
		e[i][1]+=min(e[i-1][0],e[i-1][2]);
		e[i][2]+=min(e[i-1][0],e[i-1][1]);
	}
	cout<<min(min(e[n-1][0],e[n-1][1]),e[n-1][2]);
}