[백준] C++ 1149번 : RGB 거리

풀이과정

---

집의 수 N개가 빨강-0, 초록-1, 파랑-2 각각의 색으로 칠했을 때 드는 비용을 저장하는 배열(cost[N][3])

N번째 집을 빨강, 초록, 파랑으로 칠했을 때 드는 비용의 최솟값을 저장하는 배열(d[N][3]) 을 만든다.

 

d(n) = n번째 집을 색칠하는 색과 이전의 집을 색칠한 색이 같으면 규칙에 어긋난다.

예를 들어 n번째 집을 빨간색으로 색칠한다면 이전의 집은 초록색이거나 파란색이어야한다.

비용의 최소값을 구하는 문제이기 때문에 이전 집까지  색칠한 했을 때,

초록색과 파란색 중 더 적은 비용을 선택해 준다. 

이를 식으로 나타내면 d(n) = cost[n][0] + min(d[n-1][1],d[n-1][2]가 된다.

 

최종적으로 N번째 집까지 규칙에 맞게 색칠하면 

N번째 집 빨강 -> d(n)[0] = cost[n][0] + min(d[n-1][1],d[n-1][2]

N번째 집 초록 -> d(n)[1] = cost[n][1] + min(d[n-1][0],d[n-1][2]

N번째 집 파랑 -> d(n)[2] = cost[n][2] + min(d[n-1][0],d[n-1][1] 

위의 세가지 경우가 나온다. 이 중에서 최소값을 구하면 된다.

 

 

코드

---

 

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

int main()
{
	int d[1001][3] = { 0, };
	int cost[1001][3] = { 0, };
	int iInput = 0;

	cin >> iInput;
	for (int i = 1; i <= iInput; ++i)
	{
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	}
	for (int i = 1; i <= iInput; ++i)
	{
		d[i][0] = cost[i][0] + min(d[i - 1][1], d[i - 1][2]);
		d[i][1] = cost[i][1] + min(d[i - 1][0], d[i - 1][2]);
		d[i][2] = cost[i][2] + min(d[i - 1][0], d[i - 1][1]);
	}
	
	cout << min(d[iInput][0],min(d[iInput][1], d[iInput][2]) ) << endl;

	return 0;

}