c언어 17404번 RGB거리 2 (백준)

#include <stdio.h>
#define INF 1000000000
int main(void) {
	int n;
	scanf("%d", &n);
	
	int ans = INF; //최소값
	int a[n][3]; //입력받는거
	int dp[n][3]; //dp 배열
	
	for(int i=0; i<n; i++) { //입력받기
		for(int j=0; j<3; j++) {
			scanf("%d", &a[i][j]);
			dp[i][j] = 0; //dp 배열 초기화
		}
	}
	//시작을 R
	dp[0][0] = a[0][0]; 
	dp[0][1] = INF;
	dp[0][2] = INF;
	for(int i=1; i<n; i++) {
		dp[i][0] = a[i][0] + ((dp[i-1][1] < dp[i-1][2]) ? dp[i-1][1] : dp[i-1][2]);
		dp[i][1] = a[i][1] + ((dp[i-1][0] < dp[i-1][2]) ? dp[i-1][0] : dp[i-1][2]);
		dp[i][2] = a[i][2] + ((dp[i-1][0] < dp[i-1][1]) ? dp[i-1][0] : dp[i-1][1]);
		//printf("%d %d %d\n", dp[i][0], dp[i][1], dp[i][2]);
	} //마지막은 반드시 G 또는 B이어야 한다.
	int tmp =  (dp[n-1][1] < dp[n-1][2]) ? dp[n-1][1] : dp[n-1][2];
	ans = (ans < tmp) ? ans : tmp;
	
	//시작을 G
	dp[0][1] = a[0][1];
	dp[0][0] = INF;
	dp[0][2] = INF;
	for(int i=1; i<n; i++) {
		dp[i][0] = a[i][0] + ((dp[i-1][1] < dp[i-1][2]) ? dp[i-1][1] : dp[i-1][2]);
		dp[i][1] = a[i][1] + ((dp[i-1][0] < dp[i-1][2]) ? dp[i-1][0] : dp[i-1][2]);
		dp[i][2] = a[i][2] + ((dp[i-1][0] < dp[i-1][1]) ? dp[i-1][0] : dp[i-1][1]);
	} //마지막은 반드시 R 또는 B이어야 한다.
	tmp =  (dp[n-1][0] < dp[n-1][2]) ? dp[n-1][0] : dp[n-1][2];
	ans = (ans < tmp) ? ans : tmp;
	
    //시작을 B
	dp[0][0] = INF;
	dp[0][1] = INF;
	dp[0][2] = a[0][2];
	for(int i=1; i<n; i++) {
		dp[i][0] = a[i][0] + ((dp[i-1][1] < dp[i-1][2]) ? dp[i-1][1] : dp[i-1][2]);
		dp[i][1] = a[i][1] + ((dp[i-1][0] < dp[i-1][2]) ? dp[i-1][0] : dp[i-1][2]);
		dp[i][2] = a[i][2] + ((dp[i-1][0] < dp[i-1][1]) ? dp[i-1][0] : dp[i-1][1]);
	} //마지막은 반드시 G 또는 B이어야 한다.
	tmp =  (dp[n-1][0] < dp[n-1][1]) ? dp[n-1][0] : dp[n-1][1];
	ans = (ans < tmp) ? ans : tmp;
	printf("%d", ans);
}

 

풀이 : dp

 

RGB 색깔 3종류가 있다.

 

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

 

즉 같은 열에 같은 색깔이 연속적으로 나오면 안된다!

또한 첫번째 집하고, 마지막 집의 색깔도 같아서는 안된다.

 

첫번째 집의 색깔을 하나를 고른 다음

두번 째 집부터, 마지막 집까지 dp로 모든 경우의 최솟값을 구한다.

 

dp로 두번 째 집부터 마지막 집까지의 경우의 수를 구한 다음, 마지막 집의 dp중 처음 집과 색깔이 다른 것 두개 중 최소값을 처음 집을 색칠하는 비용과 더한다. 이로써 처음에 어떠한 색깔을 칠한 집에서 시작할 때의 최소비용을 구했다.

 

이러한 과정을 나머지 색깔 2개도 같은 과정을 거치면

 

각각 처음 집의 색깔이 RGB일 때의 최소비용을 비교하여 이 중 가장 작은 것을 출력하면 된다.

 

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2