백준 알고리즘] 1149번 - RGB거리

시간 제한 : 2 초

메모리 제한 : 128 MB

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

출력

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

소스코드

#include <iostream>
#define MIN(a, b) (a<b?a:b)
using namespace std;

int n;
int cost[1001][3];
int table[1001][3];
int minCost;

void DP()
{
	for (int i = 0; i < 3; i++)
	{
		table[0][i] = cost[0][i];
	}
	if (n == 2)
	{
		int minimum;
		minimum = MIN(table[1][0], table[1][1]);
		minimum = MIN(minimum, table[1][2]);
	}
	else
	{
		for (int i = 1; i < n; i++)
		{
			table[i][0] = cost[i][0] + MIN(table[i - 1][1], table[i - 1][2]);
			table[i][1] = cost[i][1] + MIN(table[i - 1][0], table[i - 1][2]);
			table[i][2] = cost[i][2] + MIN(table[i - 1][0], table[i - 1][1]);
		}
	}
	minCost = MIN(table[n - 1][0], table[n - 1][1]);
	minCost = MIN(minCost, table[n - 1][2]);
}

int main(void)
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	}
	DP();
	cout << minCost << endl;
	return 0;
}

Tip

DP(Dynamic Programming;동적계획법)을 이용해 풀면 된다. 3색보다 집의 수가 작은 경우에는 DP를 사용할 필요가 없지만, 그 이후는 최적의 값을 점화식을 통해 구해내면 된다. 점화식은 기본적으로 아래를 따르고, 0, 1, 2는 RGB컬러를 의미한다.

table[i][0] = cost[i][0] + MIN(table[i - 1][1], table[i - 1][2]);

table[i][1] = cost[i][1] + MIN(table[i - 1][0], table[i - 1][2]);

table[i][2] = cost[i][2] + MIN(table[i - 1][0], table[i - 1][1]);