[백준] 1149번: RGB거리 - 드디어 dp 해결

정답 비율이 48%나 육박하는 dp 문제였다

 

풀이:

#include <iostream>
using namespace std;

const int R=0, G=1, B=2;

int expense[1000][3];
int houseNum;

//ans[n][color]은 n번째 집이 color인 경우에 드는 최소 비용
int ans[1000][3];

void init()
{
	cin >> houseNum;
	for(int i=0; i<houseNum; i++)
		for(int j=0; j<3; j++)
			cin >> expense[i][j];
}

int findSmall(int a, int b)
{
	if(a>=b)
		return b;
	else
		return a;
}

int getMinimumExpense()
{
	ans[0][R]= expense[0][R];
	ans[0][G]= expense[0][G];
	ans[0][B]= expense[0][B];
	
	for(int i=1; i<houseNum; i++)
	{
		ans[i][R] = expense[i][R] + findSmall(ans[i-1][G],ans[i-1][B]);
		ans[i][G] = expense[i][G] + findSmall(ans[i-1][R],ans[i-1][B]);
		ans[i][B] = expense[i][B] + findSmall(ans[i-1][R],ans[i-1][G]);
	}
	
	return findSmall(ans[houseNum-1][B],findSmall(ans[houseNum-1][R],ans[houseNum-1][G]));
}

int main() {
	init();
	cout << getMinimumExpense();
	
	return 0;
}

 

위 문제는 n번째 집에 색칠할때 드는 최소비용이 n-1번째의 집에 색칠할때 드는 최소비용과 연관이 있는 최적 부분 구조가 있어 다이나믹 프로그래밍을 통해 문제를 해결할 수 있었다.