[백준/BOJ] 백준 1149번 : RGB거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

A번째 집부터 색칠해 나아갈 때, A-1의 색과 다른 색(A가 0번째 집일 때는 어떤 색이던지 상관없다)을 고르면서 전체 집을 칠하는 비용이 최소인 비용을 구한다.

 

코드

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

int cache[1000][4];
int n;
vector<int> rvalue;
vector<int> gvalue;
vector<int> bvalue;

//home번째 집부터 색칠할때 직전에 칠했던 색이 before_color(0:직전의 색이 없는것, 1:빨강, 2:초록, 3:파랑)색인 경우, 비용의 최솟값을 구한다
int solve(int home, int before_color)
{
	int& ret = cache[home][before_color];
	
	//ret가 -1이 아니면 계산했던것이다
	if (ret != -1)
		return ret;

	//마지막 집일때 직전의 색깔과 다른 색중 비용이 작은것을 고른다
	if (home == n - 1)
	{
		if (before_color == 1)
		{
			return min(gvalue[n - 1], bvalue[n - 1]);
		}

		else if (before_color == 2)
		{
			return min(rvalue[n - 1], bvalue[n - 1]);
		}

		else if (before_color == 3)
		{
			return min(rvalue[n - 1], gvalue[n - 1]);
		}
	}

	ret = 987654321; //초기값은 매우 큰 수로 둔다

	for (int i = 1; i <= 3; i++)
	{
		//직전에 칠한 색과 다르거나 직전의 색이 없는경우
		if (before_color != i || before_color == 0)
		{
			//i색(1:빨강, 2:초록, 3:파랑)으로 칠한후 다음을 고려한다
			if (i == 1)
			{
				ret = min(ret, rvalue[home] + solve(home + 1, i));
			}

			else if (i == 2)
			{
				ret = min(ret, gvalue[home] + solve(home + 1, i));
			}
			
			else if (i == 3)
			{
				ret = min(ret, bvalue[home] + solve(home + 1, i));
			}
		}
	}

	return ret;
}

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

	//cache를 -1로 초기화 한다
	memset(cache, -1, sizeof(cache));


	int result;
	int rtemp, gtemp, btemp;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> rtemp;
		cin >> gtemp;
		cin >> btemp;

		rvalue.push_back(rtemp);
		gvalue.push_back(gtemp);
		bvalue.push_back(btemp);
	}

	//첫번째집(0번째집)부터 색칠할때(직전의 색은 없다), 비용의 최솟값을 구한다
	result = solve(0, 0);

	cout << result << "\n";

	return 0;
}