RGB거리 (백준 - 1149번)

동적계획법을 사용하는 문제였다.

 

이번 문제는 다른 문제들과 다르게 DP 테이블을 2차원 배열로 만들어줘야 한다. 한 경우(집)에 3가지 값(RGB)을 DP 테이블에 기록해야 하기 때문이다.

 

예를들어 어떤 집 N을 R로 칠할경우, 전 집 N - 1은 R로 칠할 수 없으므로 G와 B로 칠하는 비용중 가장 작은 비용을 찾아 N의 R로 칠하는 비용을 더해 DP 테이블에 기록하면 된다. N에서 G와 B도 위와 같은 방법으로 해주면 된다.

 

DP(N에서 R) = DP(N - 1에서 G나 B중 가장 작은 값) + H(N에서 R)

DP(N에서 G) = DP(N - 1에서 R나 B중 가장 작은 값) + H(N에서 G)

DP(N에서 B) = DP(N - 1에서 R나 G중 가장 작은 값) + H(N에서 B)

(DP는 DP테이블이고 H는 집들의 RGB로 칠하는 비용을 저장하는 배열이다.)

 

그리고 DP테이블 가장 마지막 집에서 RGB 값들 중 가장 작은 값을 출력해주면 그것이 모든 집을 칠하는 비용의 최솟값이 된다.

 

비용의 최솟값 = DP(마지막집 RGB 값중 가장 작은 값)

 

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

enum eRGB
{
	RED,
	GREEN,
	BLUE,
	RGB_END
};

int min(int a, int b)
{
	return a > b ? b : a;
}

int min_other(int a, int b, int c)
{
	return a > b ? (b > c ? c : b) : (a > c ? c : a);
}

int main()
{
	int input;
	cin >> input;
	
	int** costs = new int* [input];
	int** dp = new int* [input];
	for (int i = 0; i < input; ++i)
	{
		costs[i] = new int[RGB_END];
		dp[i] = new int[RGB_END];

		cin >> costs[i][RED] 
			>> costs[i][GREEN] 
			>> costs[i][BLUE];
	}

	dp[0][RED] = costs[0][RED];
	dp[0][GREEN] = costs[0][GREEN];
	dp[0][BLUE] = costs[0][BLUE];

	for (int i = 1; i < input; ++i)
	{
		dp[i][RED] = min(dp[i - 1][GREEN], dp[i - 1][BLUE]) + costs[i][RED];
		dp[i][GREEN] = min(dp[i - 1][RED], dp[i - 1][BLUE]) + costs[i][GREEN];
		dp[i][BLUE] = min(dp[i - 1][RED], dp[i - 1][GREEN]) + costs[i][BLUE];
	}

	int result = min_other(dp[input - 1][RED], dp[input - 1][GREEN], dp[input - 1][BLUE]);
	cout << result << endl;

	for (int i = 0; i < input; ++i)
	{
		delete[] costs[i];
		delete[] dp[i];
	}
	delete[] costs;
	delete[] dp;
}