C++[백준]17404번 RGB거리 2

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

17404번: RGB거리 2

 

 

솔루션

---

RGB거리를 풀 때와 다르게, 처음과 끝을 신경 써 주어야 한다..

 

그래서 처음에 무엇을 선택해서 칠했는지를 저장해 가면서 dp를 채워나갔다.

 

중간의 값들은 이전 집과 색을 다르게 칠해주면, 특정 지점의 집에 있어서 색칠 조건을 만족한다.

 

 

그래서 처음과 끝의 색을 신경 써 주어야 하는데,

 

3*3*1000 배열을 통해서

 

[첫번째 집의 색][칠하는 색깔][집]으로 생각하고 풀 수 있다.

 

마지막의 비용을 구하는 것은 

 

dp[i][j][N-1] + arr[k][N]으로 구할 수 있다. (단, k != j,i 이여야 한다.)

 

 

코드

---

#include <iostream>
using namespace std;

/*
1번 집은  2번과, 3번을 활용해서 구할 수 있음
2번 집은 1번과 3번을 활용해서 구함
3번 집은 1,2번을 활용해서 구함
*/

int arr[3][1002];
//[첫 번째 배열 중 몇번째 것을 썼는지][해당 지점의 색깔][집 번째]
int dp[3][3][1002];
int N;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[0][i] >> arr[1][i] >> arr[2][i];
	}
	
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				dp[k][j][i] = 987654321;
			}
		}
	}


	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == 1) {
				dp[j][j][i] = arr[j][i];
				continue;
			}
			if (j == 0) {
				//j가 0이라면, 1과 2중 더 큰 값으로 가져와야 함.
				
				//첫번째 집을 R로 칠했을 때, j색으로, i번째 집을 칠하는 비용
				dp[0][j][i] = min(dp[0][j][i], min(dp[0][1][i - 1], dp[0][2][i - 1]) + arr[j][i]);

				//첫번째집을 B로 칠했을 때, i번째 집을 j 색으로 칠하는 방법
				dp[1][j][i] = min(dp[1][j][i], min(dp[1][1][i - 1], dp[1][2][i - 1]) + arr[j][i]);

				//첫번째 G로 칠했으면, 
				dp[2][j][i] = min(dp[2][j][i], min(dp[2][1][i - 1], dp[2][2][i - 1]) + arr[j][i]);
			}
			if (j == 1) {
				//j가 0이라면, 1과 2중 더 큰 값으로 가져와야 함.
				
				//첫번째 집을 R로 칠했을 때, j색으로, i번째 집을 칠하는 비용
				dp[0][j][i] = min(dp[0][j][i], min(dp[0][0][i - 1], dp[0][2][i - 1]) + arr[j][i]);

				//첫번째집을 B로 칠했을 때, i번째 집을 j 색으로 칠하는 방법
				dp[1][j][i] = min(dp[1][j][i], min(dp[1][0][i - 1], dp[1][2][i - 1]) + arr[j][i]);

				//첫번째 G로 칠했으면, 
				dp[2][j][i] = min(dp[2][j][i], min(dp[2][0][i - 1], dp[2][2][i - 1]) + arr[j][i]);
			}
			if (j == 2) {
				//j가 0이라면, 1과 2중 더 큰 값으로 가져와야 함.
				
				//첫번째 집을 R로 칠했을 때, j색으로, i번째 집을 칠하는 비용
				dp[0][j][i] = min(dp[0][j][i], min(dp[0][1][i - 1], dp[0][0][i - 1]) + arr[j][i]);

				//첫번째집을 B로 칠했을 때, i번째 집을 j 색으로 칠하는 방법
				dp[1][j][i] = min(dp[1][j][i], min(dp[1][1][i - 1], dp[1][0][i - 1]) + arr[j][i]);

				//첫번째 G로 칠했으면, 
				dp[2][j][i] = min(dp[2][j][i], min(dp[2][1][i - 1], dp[2][0][i - 1]) + arr[j][i]);
			}
		}
	}

	int value = 987654321;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (i == k || j == k) continue;
				value = min(value, dp[i][j][N - 1] + arr[k][N]);
			}
		}
	}
	cout << value << "\n";
}