#17404: RGB거리 2

백준 17404번: RGB거리 2

문제:

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

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

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

입력:

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

풀이:

• 이 문제는 #1149: RGB거리의 응용 문제이다. 이 문제와 #1149: RGB거리의 차이점은 시작자리와 끝자리의 색이 같으면 안된다는 조건이 붙었다. #1149: RGB거리 문제는 집이 일자로 있다고 생각하면 되고 이 문제는 집이 원형으로 있다고 생각하면 쉽게 이해할 수 있다.
• 이 문제의 핵심은 원형이기 때문에 어디가 시작인지 끝인지 알 수 없다고 볼 수 있기 때문에 하나의 기준점을 잡고 풀면 된다. 이 문제는 기준점을 제일 처음(1)로 놓고 푸는게 편할 것이다. 기준점을 1로 놓는 다는 것은 제일 처음 색깔을 하나로 고정한 경우에서 시작해서 마지막에 최소값을 구할 때 처음 색깔을 제외하고 고르는 경우이다.
• 우선 0부터 2까지 3가지 색깔을 시작으로 지정하는 for문을 만들어준 뒤 처음 색깔을 제외한 나머지 색은 큰 수로 설정하여 지정한 처음 색깔만 뽑히도록한다. 그 이후에는 #1149: RGB거리에서 푼 방식과 똑같이 R, G, B인 경우를 나눠서 가능한 최소값을 같은 색깔을 제외한 이전 값들을 비교하여 현재 값과 더한 뒤 저장해준다. 그리고, 마지막으로 처음 고른 색깔을 제외한 마지막 경우들 중 최소값을 answer에 저장 한 뒤 출력 해준다.

코드:

#include <iostream>
#define R 0
#define G 1
#define B 2

using namespace std;

int main(){
	int n, answer = 1000001, dp[1001][3]={}, arr[1001][3]={};
	//입력
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> arr[i][R] >> arr[i][G] >> arr[i][B];
	//처음 시작이 R, G, B인 경우를 나누기 위한 for문
	for(int i = 0; i < 3; i++){
		//현재 시작 색을 제외한 모든 값들을 크게 만들어서 현재 시작 색만 고르도록 하게 초기화
		for(int j = 0; j < 3; j++) dp[1][j] = 1000001;
		dp[1][i] = arr[1][i];
		//색깔마다 최소값이 나오는 경우의 수 저장
		for(int j = 2; j <= n; j++){
			dp[j][R] = min(dp[j-1][G], dp[j-1][B])+arr[j][R];
			dp[j][G] = min(dp[j-1][R], dp[j-1][B])+arr[j][G];
			dp[j][B] = min(dp[j-1][R], dp[j-1][G])+arr[j][B];
		}
		//마지막 색상이 첫번째 색상과 다른 경우만 제외하고 최소값 정답에 저장
		if(i==R) answer = min(answer, min(dp[n][G], dp[n][B]));
		if(i==G) answer = min(answer, min(dp[n][R], dp[n][B]));
		if(i==B) answer = min(answer, min(dp[n][R], dp[n][G]));
	}
	//출력
	cout<<answer;
}