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

문제

 

 

해결

이 문제는 현재 칠할 색을 선택하는 방법만 구상하면 해결되는 문제이다.

처음에는 간단하게 "가장 작은 값을 선택하면 되지 않을까?"라고 생각하고 구현했지만 마자막 예제에서 실패가 되었다. 

아마 현재 선택한 색이 다음 선택할 색에 영향을 주어 비용이 큰 색을 선택하게 되어서 그런 것 같다. 즉 색을 선택할 때 다음 집의 색칠까지 고려해야 하는 것이다.

 

그 다음을 생각한 방법은 각 색의 색칠 비용에 대해서 현재 비용과 다음 비용의 차를 구하여 비용의 차가 가장 큰 색을 현재 치할 색으로 선택하는 것이다. 비용의 차가 크다는 것은 다음 칠을 고려했을 때 가장 효율적인 선택이라는 것을 의미하기 때문이다. 하지만 이 방법은 예제는 모두 통과할 수 있지만 정답은 아니였다. 

아마도 바로 다음 칠까지만 고려하는 것 만으로는 최적의 비용을 찾을 수 없는 것 같다.

그렇다고 두 번, 세 번 다음의 칠까지 고려하는 것은 불가능 하다고 생각하여 그냥 "모든 경로를 다 확인해보자"라는 해결 방법이 생각났고 구현해보니 가장 DP라고 부를만한 해결 방법이었다.

 

로직은 간단하다.

1. 현재 경로로 오는 가장 작은 비용을 선택한다.
2. 구한 비용과 현재 경로의 비용을 더한다.

그렇다면 현재 경로로 오는 가장 작은 비용은 어떻게 구할까?

이 해답은 굉장히 간단하다.

만약 내가 현재 빨간색을 칠한다고 하면 이전의 초록색을 칠할 때의 비용과 파랑색을 칠할 때의 비용 중 더 작은 비용이 현재 경로로 오는 가장 작은 비용이다.

 

이것을 그림으로 나타내면 이렇다.

	R	G	B
n	minCost[n][R] = min(minCost[n-1][G], minCost[n-1][B])	minCost[n][G] = min(minCost[n-1][R], minCost[n-1][B])	minCost[n][B] = min(minCost[n-1][R], minCost[n-1][G])
n + 1	minCost[n+1][R] = min(minCost[n][G], minCost[n][B])	minCost[n+1][G] = min(minCost[n][R], minCost[n][B])	minCost[n+1][B] = min(minCost[n][R], minCost[n][G])
n + 2	minCost[n+2][R] = min(minCost[n+1][G], minCost[n+1][B])	minCost[n+2][G] = min(minCost[n+1][R], minCost[n+1][B])	minCost[n+2][B] = min(minCost[n+1][R], minCost[n+1][G])

 

코드

#include<iostream>
#include <cmath>
using namespace std;

int costArr[1000][3], minCostArr[1000][3], n;

void solution()
{
	for (int i = 0; i < n; i++)
	{
		if (i == 0)
		{
			minCostArr[i][0] = costArr[i][0];
			minCostArr[i][1] = costArr[i][1];
			minCostArr[i][2] = costArr[i][2];
		}
		else
		{
			minCostArr[i][0] = min(minCostArr[i - 1][1], minCostArr[i - 1][2]) + costArr[i][0];
			minCostArr[i][1] = min(minCostArr[i - 1][0], minCostArr[i - 1][2]) + costArr[i][1];
			minCostArr[i][2] = min(minCostArr[i - 1][0], minCostArr[i - 1][1]) + costArr[i][2];
		}
	}

	cout << min(min(minCostArr[n - 1][0], minCostArr[n - 1][1]), minCostArr[n - 1][2]);
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int cost;

			cin >> cost;
			costArr[i][j] = cost;
		}
	}

	solution();
}