[백준] C++ RGB거리(1149)

 

이 문제는 이웃하는 집은 같은 색으로 칠하면 않고 비용을 최소화하는 문제이다.

 

문제풀이방법

1. 우선 세 방향에서 접근해야한다. (왼쪽, 중앙, 오른쪽)  처음 집을 빨강으로 칠하면 다음 집은 초록이나 파랑으로 칠해야한다.

2. 위와 같은 방식으로 처음집을 빨강, 초록, 파랑으로 모두 칠해보고 그 다음집에 색칠 가능한 색깔을 고려해서 다음집에 최소값을 저장한다.

 

이 그림처럼 값을 더해보고 만약 저장되어 있는 값보다 더 작다면 값을 갱신한다. 전형적인 DP문제이다.

 

#include <iostream>
#define INF 987654321;
using namespace std;

int arr[1001][3];
int DP[1001][3];

int main(void)
{
	int N = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> arr[i][j];
			DP[i][j]= INF;
		}
	}

	for (int i = 0; i < 3; i++)
	{
		DP[0][i] = arr[0][i];
	}

	
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				if (j != k && DP[i + 1][k] > DP[i][j] + arr[i + 1][k])
				{
					DP[i + 1][k] = DP[i][j] + arr[i + 1][k];
				}
			}
		}
	}

	int min = INF;

	for (int i = 0; i < 3; i++)
	{
		if (DP[N - 1][i] < min)
		{
			min = DP[N - 1][i];
		}
	}

	cout << min;

	return 0;
}