[백준 17404] RBG거리 2 (C++)

문제 링크: https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

1. 주의할 점

- "RGB거리"문제와 시작점과 끝점이 접해져 있다는 가정만 제외하면 똑같다

- 시작점과 끝점이 같다면 최소값으로 치면 안된다

 

2. 구현

- Cost[]: 집에 색을 칠했을 때 지불해야 하는 비용

- DP[N][3]: N번째 집에 R,G,B를 칠했을 때 지불해야 하는 총 비용

- 첫 번째 집에 M번을 칠했다는 가정하에 구하는 최솟값을 구하도록 한다 -> DP[1][M]에서 M을 칠하는거를 제외하고는 경우에 들지 못하도록 최댓값을 부여한다.

- DP계산이 끝난 후, 최종적으로 첫 집과 마지막의 색이 같으면 Result를 갱신하지 않는다.

#define MAX 987654321
#include <iostream>
#include <algorithm>
using namespace std;
int cost[1001][3];
int dp[1001][3];		//해당 idx까지의 총합, 마지막 색

int main() {
	int num, result = MAX;
	cin >> num;
	for (int i = 1; i <= num; i++) 
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	for (int i = 0; i < 3; i++) {
		for (int k = 0; k < 3; k++) {
			if (i == k) dp[1][k] = cost[1][k];
			else dp[1][k] = MAX;
		}
		for (int k = 2; k <= num; k++) {
			dp[k][0] = cost[k][0] + min(dp[k - 1][1], dp[k - 1][2]);
			dp[k][1] = cost[k][1] + min(dp[k - 1][0], dp[k - 1][2]);
			dp[k][2] = cost[k][2] + min(dp[k - 1][1], dp[k - 1][0]);
		}
		for (int k = 0; k < 3; k++) {
			if (i != k) 
				result = min(result, dp[num][k]);			
		}
	}
	cout << result;
	system("pause");
	return 0;
}