[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - RGB 거리2 (17404)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - RGB 거리2 (17404)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - RGB 거리2 (17404)

 

---

 

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보다 작거나 같은 자연수이다.

[ 출력 ]

• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

---

[ 코드 ]

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

// dp[n][0] : N번째 집을 빨강색으로 칠할 경우, 최소비용
// dp[n][1] : N번재 집을 초록색으로 칠할 경우, 최소비용
// dp[n][2] : N번째 집을 파랑색으로 칠할 경우, 최소비용
int dp[1001][3];
// P[n][0] : N번째 집을 빨간색으로 칠할 때의 가격
// P[n][1] : N번재 집을 초록색으로 칠할 때의 가격
// P[n][2] : N번째 집을 파란색으로 칠할 때의 가격
int P[1001][3];

int main() {
	int N; // 집의 수
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> P[i][j];
		}
	}

	int ans = 1000 * 1000 + 1;
	for (int k = 0; k < 3 ; k++) // 색깔 고정 3번 돌리기
	{
		for (int j = 0; j < 3; j++)
		{
			if (j==k) // 첫번째 색깔 고정 ex.[0]
			{
				dp[1][j] = P[1][j]; 
			}
			else // 첫번재에 나머지 색깔은 선택되면 안되기 때문에, ex. [1][2]는 엄청나게 큰 수로 정함.
			{
				dp[1][j] = 1000 * 1000 + 1;
			}
		}

		// 두번째 색깔부터 N번째 색깔까지 구하기
		for (int i = 2; i <= N; i++)
		{
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + P[i][0];
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + P[i][1];
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + P[i][2];
		}

		// ex. 첫번째 색깔이 [0]일때, 마지막 색깔은 [1][2]가 올 수 있음.
		// 결과적으로 올 수 있는 값의 최소값 구하기.
		for (int j = 0;  j < 3;  j++)
		{
			if (j == k) // ex. dp[n][0]은 사용될 수 없음 (같은색이기 때문)
			{
				continue;
			}
			ans = min(ans, dp[N][j]);
		}

	}
	
	cout << ans;
	return 0;

}