[17404번] RGB거리 2

www.acmicpc.net/problem/17404

17404번: RGB거리 2

kau-algorithm.tistory.com/49

[모의 테스트 풀이] RGB거리

RGB 거리와 내용은 같으나, '1번 집과 N번째 집의 색이 달라야한다.'는 조건이 추가됐습니다.

 

동적 계획법을 사용하여 각 경로마다 최소값을 저장해가면서 풀어야합니다.

 

또한 새로 추가된 조건을 만족하기 위해

 

'R로 시작했을 때의 최소값',

'G로 시작했을 때의 최소값',

'B로 시작했을 때의 최소값'

 

모두를 각각 구해야 합니다.

 

R로 시작하기 위해서는 R을 제외한 나머지 G, B의 첫번째 집 비용을 1000 이상으로 설정해주면 됩니다.

(문제에서 제시된 집 하나의 최대 비용이 1000이기 때문입니다.)

 

R로 시작하는 경로에서는 3가지 최소값을 구할 수 있습니다.

 

'R로 시작해서 R로 끝나는 최소값'

'R로 시작해서 G로 끝나는 최소값'

'R로 시작해서 B로 끝나는 최소값'

 

여기서 첫번째 집과 끝나는 집의 색은 같으면 안된다는 조건이 있으므로

같은 색으로 끝나는 최소값은 비교 대상에서 제외해주시면 됩니다.

 

'R로 시작해서 R로 끝나는 최소값'

'R로 시작해서 G로 끝나는 최소값'

'R로 시작해서 B로 끝나는 최소값'

 

'G로 시작해서 R로 끝나는 최소값'

'G로 시작해서 G로 끝나는 최소값'

'G로 시작해서 B로 끝나는 최소값'

 

'B로 시작해서 R로 끝나는 최소값'

'B로 시작해서 G로 끝나는 최소값'

'B로 시작해서 B로 끝나는 최소값'

 

이렇게 구한 6개의 최소값 중 가장 작은 값을 출력해주시면 됩니다!

 

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

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

int N;
int minCost[1001][3];
int house[1001][3];
int minRes;

#define MAX 1000001;

int main()
{
	cin >> N;

	minRes = MAX;

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

	for (int k = 0; k < 3; k++)
	{
		for (int m = 0; m < 3; m++)
		{
			if (k == m)
			{
				minCost[1][m] = house[1][m];
			}

			else
			{
				minCost[1][m] = MAX;
			}
		}

		for (int i = 2; i <= N; i++)
		{
			minCost[i][0] = house[i][0] + min(minCost[i - 1][1], minCost[i - 1][2]);
			minCost[i][1] = house[i][1] + min(minCost[i - 1][0], minCost[i - 1][2]);
			minCost[i][2] = house[i][2] + min(minCost[i - 1][0], minCost[i - 1][1]);
		}

		for (int i = 0; i < 3; i++)
		{
			if (k != i)
			{
				minRes = min(minRes, minCost[N][i]);
			}
		}
	}
	
	cout << minRes << "\n";

	return 0;
}