[ DP - 1149 ] RGB거리(C++)

문제

---

접근법

 

DP 문제이기에 직접 하나하나 해 보면서 규칙을 찾고자 하였다. 하지만, 색상에 따른 Cost를 기준으로 규칙을 찾기에는 각 Cost는 변경되고, 동일한 Cost에 대한 처리가 힘들어 포기하였다.

 

Cost가 결정되는 기준은 결국 각각의 집이 칠하고자 하는 RGB색상에 의해 결정된다.

집의 색상을 결정하는 규칙은 결국 1번째 집부터 시작하여 다음집과 색상이 안겹치면 된다. 이 점에서 나올수 있는 경우의 수를 생각 해 보면, 다음 집의 색상이 R이 되기 위해선 이전에는 G,B가 되어야 한다. 다음 집의 색상이 B이 되기 위해선 이전에는 R,G가 되어야 하며, 다음 집의 색상이 G이 되기 위해선 이전에는 R,B가 되어야 한다.

 

	for (s32_I = 1; s32_I <= s32_N; s32_I++)
	{
		cin >> ars32_Cost[0] >> ars32_Cost[1] >> ars32_Cost[2];

		ars32_House[s32_I][0] = min(ars32_House[s32_I - 1][1], ars32_House[s32_I - 1][2]) + ars32_Cost[0];
		ars32_House[s32_I][1] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][2]) + ars32_Cost[1];
		ars32_House[s32_I][2] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][1]) + ars32_Cost[2];

	}

 

따라서 각각의 색상에 따른 최소비용을 매번 계산한 후 최종적으로 가장 비용이 적은 것을 선택하면 된다.

 

---

정답

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

int32_t ars32_House[1001][3]; // 각각의 색으로 칠했을 때의 최소 비용을 저장
int32_t ars32_Cost[3];		  // 각 집의 색상에 따른 비용 저장

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int32_t s32_N, s32_I;
	cin >> s32_N;

	ars32_House[0][0] = 0;
	ars32_House[0][1] = 0;
	ars32_House[0][2] = 0;

	for (s32_I = 1; s32_I <= s32_N; s32_I++)
	{
		cin >> ars32_Cost[0] >> ars32_Cost[1] >> ars32_Cost[2];

		ars32_House[s32_I][0] = min(ars32_House[s32_I - 1][1], ars32_House[s32_I - 1][2]) + ars32_Cost[0];
		ars32_House[s32_I][1] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][2]) + ars32_Cost[1];
		ars32_House[s32_I][2] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][1]) + ars32_Cost[2];

	}

	cout << min(ars32_House[s32_N][0], min(ars32_House[s32_N][1], ars32_House[s32_N][2])) << endl;

	return 0;
}