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

 

 

 

<코드>

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

#define MAX 1000000
int N;
int color[1001][3];
int dp[1001][3];
int ans = MAX;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> color[i][0] >> color[i][1] >> color[i][2];

	for (int RGB = 0; RGB <= 2; RGB++) // RGB : 1번 집의 색
	{
		// 1번집에 지정된 색 이외의 색은 MAX로 지정하여 dp할때 선택되지 않도록 함
		for (int i = 0; i <= 2; i++) 
		{
			if (i == RGB) dp[1][i] = color[1][i];
			else dp[1][i] = MAX;
		}

		// DP
		for (int i = 2; i <= N; i++)
		{
			dp[i][0] = color[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = color[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
			dp[i][2] = color[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		// 1번집 색과 N번집 색이 겹치지 않게 함
		for (int i = 0; i <= 2; i++)
		{
			if (i == RGB) continue;
			else ans = min(ans, dp[N][i]);
		}
	}
	cout << ans;
}

 

풀이 방법

 

문제 백준 1149번 - RGB거리의 경우엔 1번 집과 N번 집의 색이 겹쳐도 됐으므로 초기값 세팅 후 2~N까지 dp 해주면 풀리는 문제였다. 하지만 이번 문제는 1번 집과 N번 집의 색이 겹쳐지면 안 되는 원형문 제이다.

 

따라서 1번 집에 빨강, 초록, 파랑을 각각 색칠하는 경우를 나눠서 생각해야 하므로.

1번 집에 빨강을 칠하는 경우를 살펴보자면 2번집을 선택할 때 1번집 색을 초록이나 파랑색을 선택하지 않도록 1번집에 초록이나 파랑을 선택하는 dp값을 MAX로 지정하여 선택이 되지 않도록 한다.

 

 

 

www.acmicpc.net/problem/17404

17404번: RGB거리 2