[동적 계획법 3 단계] 백준 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보다 작거나 같은 자연수이다.

출력

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

 

 

RGB 거리 1과 비교하면 N이 1과 달라야 한다는 것이 추가됨.

따라서 1이 R로 시작, G로 시작 B로 시작으로 케이스 분류하고 

N 도착 시에 1이 R로 시작 했다면 G와 B중 최소, B로 시작했다면 R과 G중 최소 G로 시작했다면 R과 B중 최소로 6가지에 대한 최솟값을 선택하면 된다.

 

그렇다면 1이 R,G,B로 각각 시작하는 상황을 어떻게 만들 것인가 

for문으로 3번 돌면서 R일때는 R에만 값을 넣어주고 나머지에는 큰 값을 넣어서 2로부터 G와 B가 선택 당하지 않도록 한다.

하지만 2가 R인 경우 G와 B가 큰 값이여도 선택되게 되는데 어차피 2가 R인경우는 큰 값으로 3에서 선택당하지 않을 것이므로 배제 된다. 

따라서 무조건 1이 R인 경우가 선택되게 유도할 수 있고 다만 N에 다다랐을 때 N이 R이면서 최소일 수 있는데 

(N-1이 G, B라면 N이 R을 선택해도 되는 것이므로)

최소 값을 구할 때 i ( 1의 색깔과)  j (N의 색깔) 이 다른 경우에만 최소 값을 비교해주면 된다.

 

#include <iostream>
#include <vector>
#include<string.h>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;

int color[3][1001];
int dp[3][1001];
int N;
int main() {
	cin >> N;

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


	int ans = 1000 * 1000 + 1;
	
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			//현재 색과 다른 것은 큰 값
			if (i == j)
			{
				dp[j][1] = color[j][1];
			}
			else
			{
				dp[j][1] = 1000 * 1000 + 1;
			}
		}

		for (int j = 2; j <= N; j++)
		{
			// 2부터 1과 색이 일치하게 되면 큰 값이 들어가게 된다.
			dp[0][j] = min(dp[1][j - 1], dp[2][j - 1]) + color[0][j];
			dp[1][j] = min(dp[0][j - 1], dp[2][j - 1]) + color[1][j];
			dp[2][j] = min(dp[1][j - 1], dp[0][j - 1]) + color[2][j];
		}
		
		// 1이 0 일 때  1 , 2에는 10001을 넣어서 2가 1, 2 색깔일 때 이전 색깔로 0 을 선택하게 하고
		// 그 이후 dp[0][k] 에서 dp[1][k-1] , dp[2][k-1] 중에 고르는 것이므로 더 작은 수가 될 수도 있음.
	
		for (int j = 0; j < 3; j++)
		{
			if (i == j)
			{
				continue;
			}
			if (ans > dp[j][N])
			{
				ans = dp[j][N];
			}
		}
	}
	cout << ans << endl;
	
}