백준 1149 - RGB 거리

본문제의 요구사항은 다음과 같다. 거리에 N 개의 집을 색칠해야 하는데 R,G,B 중 하나의 색으로 칠해야 한다. 단 모든 연속되는 집들은 서로 다른 색으로 색칠되어야 한다. 각 집별로 색깔별로 칠하는비용이 주어졌을때 가장 최소 비용이 드는 경우의 비용이 얼마인지 구해야 한다.

집이 최대 1000 개 이므로 단순히 완전 탐색 ( 모든 경우를 일일이 다 따져보는것 ) 으로는 해를 구할 수 없다.

적절한 점화식을 유도하고 재귀호출을 통해 계산하되 중복 계산이 발생하지 않도록 메모제이션을 하는 방식으로 답을 구할수 있다.

 

1번째부터 N 번 째까지 최소 비용을 구하는 함수를 F(1,N) 이라고 정의한다면 다음과 같이 표현할 수 있다.

  F(1,N) = min ( R[1] + F(2,N) , G[1] + F(2,N) , B[1] + F(2,N))

위 수식을 기반으로 재귀호출 함수를 구현하고 메모제이션을 도입하여 코딩을 해보면 아래와 같다

 

#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int gData[1000][3];
int gMemo[1000][3] = { -1, };

#define INF 987654321

int getMinCost(int previous, int index, int &nrHouse);

int main()
{
	int nrHouse;
	scanf("%d", &nrHouse);

	memset(gMemo, -1, sizeof(gMemo));

	for (int i = 0; i < nrHouse; i++)
	{
		scanf("%d%d%d", &gData[i][0], &gData[i][1], &gData[i][2]);
	}
	int result = INF;
	result = min(result, gData[0][0] + getMinCost(0, 1, nrHouse));
	result = min(result, gData[0][1] + getMinCost(1, 1, nrHouse));
	result = min(result, gData[0][2] + getMinCost(2, 1, nrHouse));

	cout << result << endl;
}

int getMinCost(int previous, int index, int &nrHouse)
{
	if (index == nrHouse) return 0;

	if (gMemo[index][previous] != -1) return gMemo[index][previous];

	int result = INF;
	for (int i = 0; i < 3; i++)
	{
		if (i != previous)
			result = min(result, gData[index][i] + getMinCost(i, index + 1, nrHouse));
	}
	gMemo[index][previous] = result;
	return result;
}

R 에 해당 하는 숫자는 0 , G 는 1 , B 는 2 로 매핑되고 각 집들은 이전집들과 서로 다른 색을 선택해야 하므로 이전 집 색칠 값이 함수 ( getMinCost ) 로 전달되어야 한다.

현재 배열의 인덱스와 이전진 색칠값을 기반으로 계산 결과를 메모해놓으면 중복 계산이 방지되어 시간초과를 예방할 수 있다.