[모의 테스트 풀이] RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

바로 두번째 풀이 시작하겠습니다. 해당 문제는, 다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

이름이 참 거창해 보이지만 별거 없습니다.

이거 만드신 분도 연구비를 따내려고 최대한 멋있는 이름을 붙였다는 카더라가 있습니다...

 

다이나믹 프로그래밍의 정의를 살펴보면 다음과 같습니다.

큰 문제를 작은 문제들로 나누어 풀고, 작은 문제들은 단 한번만 풀도록 하는 알고리즘

 

하지만 저는 다음과 같이 편하게 생각하기도 합니다.

써먹을 수 있는건 기억해놓고 다시 써먹기

 

무엇을 기억해야하고 무엇을 다시 써먹어야 할지, 이 문제를 풀면서 이해해봅시다.

 

[다이나믹 프로그래밍 적용시키기 - 예제와 함께]

참 까탈스러운 주민들이 아닐 수 없습니다.. 대체 무엇을 위해 이 주민들은 자신의 집을 RGB로 칠해야 할까요? 조건과 예제를 통해 찬찬히 살펴보겠습니다.

 

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

간단히 말하자면, 윗집과 아랫집은 색깔이 달라야 하고, 예제 입력으로는 각 집을 R, G, B로 칠하는 비용이 주어집니다.

예제 입력을 다음과 같이 생각해 볼 수 있겠습니다.

 

	Red 칠하는 비용	Green칠하는 비용	Blue칠하는 비용
1번 집	26	40	83
2번 집	49	60	57
3번 집	13	89	99

 

조건에서는 윗집과 색깔이 다르며 모든 집을 최소 비용으로 칠하라고 했습니다.

그럼, 다음과 같이 생각해보면 어떨까요?

 

2번 집을 빨강으로 칠하려면, 1번 집을 초록 혹은 파랑으로 칠하는 비용 중 작은 비용을 칠했으면 된다.
2번 집을 초록으로 칠하려면, 1번 집을 빨강 혹은 파랑으로 칠하는 비용 중 작은 비용을 칠했으면 된다.
2번 집을 파랑으로 칠하려면, 1번 집을 빨강 혹은 초록으로 칠하는 비용 중 작은 비용을 칠했으면 된다. 

말장난같지만, 이는 맞는말입니다. 아직 이해가 안된다면, 2번 집을 칠하는 예시를 들어보겠습니다.

 

2번 집을 빨강으로 칠해보는 경우를 생각해보죠. 

 

당장 2번집의 페인트비는 49입니다.

1번 집을 초록으로 칠했었다고 가정하면, 2번째 집에 빨강을 칠한 전체 페인트 비용은 49에 40을 더한 89입니다.

1번 집을 파랑으로 칠했었다고 가정하면, 2번째 집에 빨강을 칠한 전체 페인트 비용은 49에 83을 더한(계산기 꺼내는중..)  132입니다.

 

그럼 집주인은 당연히, 2번 집에는 빨강, 1번집에는 초록을 칠했을 것입니다. 

 

하지만 지금은 2번집에 빨강을 칠했음을 전제하는 것이므로, 2번집에 비용을 기억해줍니다. 이것이 다이나믹 프로그래밍의 핵심인 메모이제이션(memoization)입니다.

	Red 칠하는 비용	Green칠하는 비용	Blue칠하는 비용
1번 집	26	40	83
2번 집	89	60	57

 

2번집에 초록을 칠했다고 했을 때 1번집에는 무슨 페인트를 칠했어야 개이득인지 확인차 살펴볼까요?

스스로 한번 해보시고 답을 확인해보세요.

그럼 같이 확인해 보겠습니다.

 

2번집의 초록 칠하는 비용은 60입니다.
1번 집에 빨강을 칠했었다면, 2번째 집에 초록을 칠한 전체 비용은 60 + 26 = 86일 것입니다.

1번 집에 파랑을 칠했었다면, 2번째 집에 초록을 칠한 전체 비용은 83 + 60 = 143일 것입니다.

 

그럼 당연히, 최소비용은 89를 선택할 수 있겠습니다.

2번 집을 파랑으로 칠하는 비용의 과정은 생략하겠습니다.

2번 집까지 최소한의 비용으로 칠하는 비용은 다음과 같이 고칠 수 있겠습니다.

 

	Red 칠하는 비용	Green칠하는 비용	Blue칠하는 비용
1번 집	26	40	83
2번 집	86	89	83

 

우리의 집은 3층까지 있었죠. 지금까지 구한 2번 집까지의 최소비용을 통해서 3번 집까지의 최소 비용을 구하면 다음과 같이 되겠습니다.

 

	Red 칠하는 비용	Green칠하는 비용	Blue칠하는 비용
1번 집	26	40	83
2번 집	86	89	83
3번 집	13  96	89  172	99  185

결국 이 건물은, 최소비용 96으로 조건을 만족하며 색깔을 칠할 수 있게 되었습니다.

 

[다이나믹 프로그래밍 적용시키기 - 코드와 함께]

#include <iostream>
using namespace std;

int Min(int a, int b)//값비교하는 함수
{
	return a < b ? a : b;
}
int main()
{
	int n;
	int Houses[1000][3] = { 0, };//index[0]은 층수, [1]은 호수를 의미한다.
	int MinNum = 10000;//최솟값을 구하기 위한 함수.
	cin >> T;

	for (int k = 0; k < T; k++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> Houses[k][j];
		}
	}

	for (int House = 1; House <= n; House++)
	{
		for (int Color = 0; Color < 3; Color++)
		{
			if (Color == 0)//R이면 윗집의 G,B중 비용이 적은 것을 칠해야함
				Houses[House][Color] += Min(Houses[House - 1][1], Houses[House - 1][2]);
			else if (Color == 1)//G이면 윗집의 R,B중 비용이 적은 것을 칠해야함
				Houses[House][Color] += Min(Houses[House - 1][0], Houses[House - 1][2]);
			else //B이면 윗집의 R,G중 비용이 적은 것을 칠해야함
				Houses[House][Color] += Min(Houses[House - 1][0], Houses[House - 1][1]);
		}
	}

	for (int i = 0; i < 3; i++)
	{
		if (MinNum > Houses[n][i])
		{
			MinNum = Houses[n][i];//계산 값 중 가장 최솟값을 출력한다.
		}
	}
	cout << MinNum;
	return 0;
}

약간 복잡해보이긴 하지만, 예제 설명 그대로입니다.

Houses를 2차원 배열로 선언하여 RGB색깔 도색 비용을 저장하고,

두번째 for문을 통해 비교하여 마지막 결과 중 최소값을 출력합니다.