백준 1149 RGB거리 (C++)

탑다운, 바텀업 방식 첨부

세가지 조건을 합쳐보면 결국 한 집 기준으로 좌 우 집이랑 같은 색이 안된다는 말.

빨 파 빨 파 빨 파 빨 파 이런식으로 존재해도 조건은 만족한다.

어떤 위치의 집이 어떤 색일때의 경우를 따져 보아야 최소 비용을 구할 수 있을 것이기에 dp를 사용한다.

 

Top down 방식 풀이

#include <iostream>
#include <algorithm>
#include<cmath>
#define BIGNUM 2100000000
using namespace std;
struct house {
	int r;
	int g;
	int b;
};
int inputnum;
house arr[1001];
int dp[1001][3];// 0=r 1=g 2=b
int rec(int index, int num, int check);
int main()
{
	cin >> inputnum;
	arr[0].r = 0;
	arr[0].g = 0;
	arr[0].b = 0;

	for (int i = 0; i < inputnum; i++)
	{
		cin >> arr[i].r >> arr[i].g >> arr[i].b;
	}
	fill(&dp[0][0], &dp[1000][2], BIGNUM);
	cout << min(min(rec(0, 0, 0),rec(0,0,1)),rec(0,0,2));

}
int rec(int index, int num, int check)
{
	if (index == inputnum - 1)
	{
		if (check == 0) return arr[index].r;
		else if (check == 1) return arr[index].g;
		else if (check == 2) return arr[index].b;
	}
	if (index >= inputnum) return BIGNUM;
	if (dp[index][check] != BIGNUM) return dp[index][check];
	int temp;
    
	if (check == 0)
    	temp = arr[index].r+ min(rec(index + 1, num + arr[index].r, 1), rec(index + 1, num + arr[index].r, 2));
	else if (check == 1)
		temp = arr[index].g+min(rec(index + 1, num + arr[index].g, 0), rec(index + 1, num + arr[index].g, 2));
	else if (check == 2)
		temp = arr[index].b+min(rec(index + 1, num + arr[index].b, 0), rec(index + 1, num + arr[index].b, 1));
        
	//cout << "index: " << index << " num: " << num << " check: " << check << " temp: "<<temp<< endl;
	dp[index][check] = temp;
	return temp;
}

첫 집의 색이 빨강인경우 초록인경우 파랑인경우 중 가장 비용이 작은 경우를 출력해준다.

해당 인덱스의 집에 어떤 색을 칠했는지를 다음 함수호출의 인자로 적어 주어서 좌우로 색이 겹치지 않도록 해준다.

그중 작은 값을 반환해 dp 배열에 기록해둔다.

최소 비용을 찾고 있기에 dp 배열은 매우 큰 값으로 초기화해둔다.

 

Bottom-up 풀이

#include <iostream>
#include <algorithm>
#include<cmath>
#define BIGNUM 2100000000
using namespace std;
struct house {
	int r;
	int g;
	int b;
};
int inputnum;
house arr[1001];
int dp[1001][3];// 0=r 1=g 2=b
int main()
{
	cin >> inputnum;
	for (int i = 0; i < inputnum; i++)
	{
		cin >> arr[i].r >> arr[i].g >> arr[i].b;
	}
	dp[0][0] = arr[0].r;
	dp[0][1] = arr[0].g;
	dp[0][2] = arr[0].b;
	for (int i = 1; i < inputnum; i++)
	{
		dp[i][0] = arr[i].r+min(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = arr[i].g + min(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = arr[i].b + min(dp[i - 1][0], dp[i - 1][1]);
	}
	cout << min(dp[inputnum - 1][2],min(dp[inputnum - 1][0], dp[inputnum - 1][1]));

	

}

첫 집의 색깔별 기록을 dp[0]에 저장해둔 뒤 dp[1]부터 해당 집을 색깔별로 칠할 때의 최소 비용을

한 집씩 넘어가며 차근차근 구한다.

dp[마지막 집의 인덱스] 에 해당 집을 어떤 색으로 칠하는가에 따른 최소 비용이 기록되어 있으므로

마지막 집을 R,G,B 색상으로 칠할때의 최소 비용중 min 값을 출력해준다.