[C++] 백준 1149번 RGB거리

 

1) 문제설명

백준 Online Judge RGB거리

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

1149번: RGB거리

 

2) 아이디어

DP를 이중 배열로 선언한다. DP [1][X] 에는 RED를 DP [2][X]에는 GREEN을 DP [3][X]에는 BLUE를 선택했을 경우로 나눈다.

DP [1][X]에서는 DP [2][X-1] or DP [3][X-1]에 RED를 더했을 때의 최솟값을

DP [2][X]에서는 DP [3][X-1] or DP [1][X-1]에 GREEN를 더했을 때의 최솟값을

DP [3][X]에서는 DP [1][X-1] or DP [2][X-1]에 BLUE를 더했을 때의 최솟값을 저장한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
long long dp[1001][1001];

int main() {
	int n;
	cin >> n;
	long long* red , *green, *blue;
	red = (long long*)malloc(sizeof(long long) * (n+1));
	green = (long long*)malloc(sizeof(long long) * (n+1));
	blue = (long long*)malloc(sizeof(long long) * (n+1));

	for (int i = 1; i <= n; i++) {
		cin >> red[i] >> green[i] >> blue[i];
	}

	dp[1][0] = 0; // red
	dp[2][0] = 0; // green
	dp[3][0] = 0; // blue

	for (int i = 1; i <= n; i++) {
		dp[1][i] = min(red[i] + dp[2][i - 1], red[i] + dp[3][i - 1]); // 전에 green 이나 blue를 택했을 경우
		dp[2][i] = min(green[i] + dp[1][i - 1], green[i] + dp[3][i - 1]); // 전에 red 나 blue를 택했을 경우
		dp[3][i] = min(blue[i] + dp[1][i - 1], blue[i] + dp[2][i - 1]); // 전에 red 나 green을 택했을 경우
		if (i == n) {
			cout << min(min(dp[1][i], dp[2][i]), dp[3][i]);
		}
	}
	
}

처음에 RGB 색 중에서 작은 값을 선택하고 그 값을 선택했을 경우 중복선택을 하지 않기 위해서 현재 그 값에 1001을 넣어주어 (RGB의 최댓값은 1000 이기 때문) 선택하지 않도록 구현을 해서 실패했다.