boj, 백준) 17404. RGB거리 2 (C/C++)

1. 문제 링크

www.acmicpc.net/problem/17404

17404번: RGB거리 2

2. 문제 개요

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

 

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

 

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

3. 문제 힌트

DP문제.

 

원래대로 비교, 즉, 전수조사하려면 3^N 2^N에 비례하는 시간이 소요됨.(N-1번째 색깔은 당연히 안 고르기 때문)

최소인 비용(최적)만 가지고 가는 방법이 필요..

 

위에서 첫번째, 두 번째에 의해서 약간 원형? 같은 느낌이 되는데,

이 조건을 제거한다면 단순히

 

2번째 빨간색 = min(1번째 초록색, 1번째 파란색) + 2번째 빨간색 칠하는 비용

으로 쉽게 구할 수 있다. 이런방법으로 N까지 이어나가면 된다. 하지만 이 문제는 원형처럼 마지막도 첫 번째와 같은 색을 하면 안 되는 조건이 달려있다.

 

기존의 방식으로 한다면 N번째 집을 칠할 때, 첫번째에 무슨 색을 칠했는지 알 수 있는 방법이 없다. 아는 것은 어떤 색을 칠했는지는 모르지만, 최소(최적)의 비용 값만 안다.

 

첫 번째 집이 무슨 색인지 안다면 문제를 해결할 수 있을 듯한데...

 

4. 문제 풀이

dp배열에 첫 번째 집이 무슨 색이었는지 기록하자.

 

dp[첫번째 집 색깔][1,2, ..., i, ..., N][i번째 집의 색깔]로 정의하자.

 

첫번째와 N번째 케이스만 수정해주면 된다.

 

첫번째 집이 ( 0 : 빨간색 )인 경우,

dp[0][1][0]이 되어야 하고

첫 번째 집이 빨간색이지만 초록색, 빨간색으로 색칠된 경우는 당연히 말이 안 되므로 dp[0][1][1], dp[0][1][2] =987654321과 같은 충분히 큰 값을 넣어주자.

 

마지막도 마찬가지로

dp[0][N][0], dp[1][N][1], dp[2][N][2]는 처음과 마지막이 색깔이 같다는 것을 의미하고, 여기도 고려해선 안 되기 때문에 987654321과 같은 충분히 큰 값을 넣어주도록 하자.

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

int n, ans = 987654321;
int val[1001][3];
int dp[3][1001][3];

int main()
{
	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) 
		scanf("%d %d %d", &val[i][0], &val[i][1], &val[i][2]);
	
	dp[0][1][0] = val[1][0];
	dp[1][1][1] = val[1][1];
	dp[2][1][2] = val[1][2];

	dp[0][1][1] = dp[0][1][2] = dp[1][1][0] = dp[1][1][2] = dp[2][1][0] = dp[2][1][1] = 987654321;

	for (int i = 2; i <= n; ++i) {

		
			dp[0][i][0] = min(dp[0][i - 1][1], dp[0][i - 1][2]) + val[i][0];
			dp[0][i][1] = min(dp[0][i - 1][0], dp[0][i - 1][2]) + val[i][1];
			dp[0][i][2] = min(dp[0][i - 1][0], dp[0][i - 1][1]) + val[i][2];

			dp[1][i][0] = min(dp[1][i - 1][1], dp[1][i - 1][2]) + val[i][0];
			dp[1][i][1] = min(dp[1][i - 1][0], dp[1][i - 1][2]) + val[i][1];
			dp[1][i][2] = min(dp[1][i - 1][0], dp[1][i - 1][1]) + val[i][2];

			dp[2][i][0] = min(dp[2][i - 1][1], dp[2][i - 1][2]) + val[i][0];
			dp[2][i][1] = min(dp[2][i - 1][0], dp[2][i - 1][2]) + val[i][1];
			dp[2][i][2] = min(dp[2][i - 1][0], dp[2][i - 1][1]) + val[i][2];
			
			if(i == 2)
			{
				dp[0][i][0] = dp[1][i][1] = dp[2][i][2] = 987654321;
			}

			if (i == n) {
				dp[0][i][0] = dp[1][i][1] = dp[2][i][2] =  987654321;
			}
	}

	for (int i = 0; i < 3; ++i) 
		for (int j = 0; j < 3; ++j) 
			ans = min(ans, dp[i][n][j]);
		
	printf("%d", ans);
	return 0;
}

 

6. 결과