[ C++ 백준 17404 ] RGB 거리 2

---

 

 

 

DP 문제이다.

전에 풀다가 어려워서 포기했었는데

이전 문제에서 DP도 풀었겠다.

재도전해보았고, 결국 해결했다.

( 40분 정도 소요 )

 

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int HousePaintCost[1001][4];
int DP[1001][3][3];
// 1000, 현재값 - 0, 1, 2, 시작값 - 0, 1, 2

int main()
{
	int houseCnt;
	cin >> houseCnt;

	memset(DP, 0x3f, sizeof(DP));

	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			DP[0][i][j] = 0;

	int R, G, B;
	for (int i = 1; i <= houseCnt; ++i)
	{
		cin >> R >> G >> B;
		HousePaintCost[i][0] = R;
		HousePaintCost[i][1] = G;
		HousePaintCost[i][2] = B;

		for (int j = 0; j < 3; ++j) //현재값
		{
			for (int k = 0; k < 3; ++k) //시작값 다른 것1
			{
				if (i == houseCnt && k == j) //끝값과 시작값이 같으면 계산 X
					continue;
				if (i == 2 && k == j) //1과 2의 시작값이 같으면 계산 X
					continue;
				if (i == 1 && k != j)
					continue;

				DP[i][j][k] = min(DP[i][j][k],
					DP[i - 1][(j + 1) % 3][k] + HousePaintCost[i][j]);

				DP[i][j][k] = min(DP[i][j][k],
					DP[i - 1][(j + 2) % 3][k] + HousePaintCost[i][j]);
			}
		}
	}

	int answer = 1000000;
	for (int j = 0; j < 3; ++j)			// 끝 값
	{
		for (int k = 0; k < 3; ++k)		// 시작 값
		{
			if (j == k) continue;
			answer = min(answer, DP[houseCnt][j][k]);
		}
	}
	cout << answer;
}

 

간단하게 얘기해서 전부 도는 코드이다.

문제에서 나온 조건들은 if문을 통해 걸러 주었다.

 

DP 배열은

현 값 위치 0~1000,

현재 RGB 무엇을 채색하는지 0~2,

시작 RGB는 무엇인지 0~2,

배열로 DP[1001][3][3]으로 선언했다.

0 = 빨강, 1 = 초록, 2 = 파랑이다.