boj 1149 - RGB 거리(Dynamic Programming )

1. 문제 해석

1. N개의 집이 있음 

2. 집에 RGB 색상을 칠할 수 있음 

3. 칠하는 색상마다 비용이 존재, 집마다 칠하는 비용은 제각각 다르다.

4. 이웃하는 집에는 서로 같은 색깔을 칠할 수 없다. 즉, 

R G B 조합 혹은

R G R 조합과 같은 형태

5.집의 수는 2개이상 1000개 이하 / 집을 칠하는 비용은 1000보다 작은 자연수 

 

2. 처음 들었던 생각

문제를 접근했을때

a. 브루트 포스

경우의 수는 3x2x2....이고 이것을 브루트 포스로 전체 다 순회한다면 지수 복잡도 -> 말이 안됨 

b. 그리디

처음에 가장 작은 선택지를 사용한다.

하지만 다음과 같은 경우에 대처할 수 없음

첫번째 집에서 1, 100, 100일때 당연히 1을 선택하는게 현명해 보이지만

두번째 집에서 1, 1000, 1000이면 첫번째에 100을 선택하고 다음에 1을 선택해야 최소가 된다. 

-> 그리디도 아님 

 

3. 문제 해결 방법

a. 생각을 어떻게 처리해야 할지 잘 모르겠어서 해법 힌트를 보니 DP 문제라는 것을 알게 됨

b.하지만 여전히 DP를 어떻게 활용해야 할지 잘 몰랐음 

-> 피보나치와 같은 1차원 배열 형태만 알고 있다 보니 어떻게 처리해야 할지 문제 확장이 안됨 

-> 1차원 배열 관점에서 단계별로 dp를 둬서 해당 단계에서의 가장 최솟값을 저장하면 되나? 라고 생각했지만 두번째 이유처럼

    1차원배열로는 해당 단계에서 최솟값이였던게 다음 단계에서 최솟값임을 보장할 수 없음 

 

   dp[i] = i번째 집까지의 최소 비용

   이렇게만 두면 i번째 집의 색이 무엇인지 알 수 없다. + 해당 루트가 다음 번 최솟값 보장 x

   다음 집을 칠할 때는 직전 집 색 정보가 필요함

   그래서 1차원 상태만으로는 부족하고, 색 정보까지 포함한 2차원 dp가 필요함

 

 

 

c. dp를 각 rgb 원소에 대해서 저장하여 r칠했을때의 최소, g 칠했을때의 최소, b 칠했을때의 최소를 각각 구해 나중에 최종적으로       비용이 가장 적게 드는 마지막 구하고자 하는 단계에서 비교하여 최소 비용 출력

 

dp[i][0] : i번째 집이 빨강일 때, 0번 집부터 i번 집까지의 최소 비용

dp[i][1] : i번째 집을 초록일 때, 0번 집부터 i번 집까지의 최소 비용

dp[i][2] : i번째 집을 파랑일 때, 0번 집부터 i번 집까지의 최소 비용

 

4. 소스코드

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

int main() {
	int n;

	cin>>n;
	
	vector<vector<int>> cost(n,vector<int>(3));

	for(int i=0; i<n; i++)
	{
		int r,g,b;
		cin>>r>>g>>b;
		cost[i][0] = r;
		cost[i][1] = g;
		cost[i][2] = b;
	}

	vector<vector<int>> dp(n,vector<int>(3));

	dp[0][0] = cost[0][0];
	dp[0][1] = cost[0][1];
	dp[0][2] = cost[0][2];

	for(int i=1; i<n; i++)
	{
		//현재가 r 일때 이전에는 g나 b였어야 함, 그중에 지금까지의 최소
		dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]);
		dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2]);
		dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1]);
	}

	cout<<min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);

 

5.배운 점

DP 문제가 단순 점화식의 형태의 단일화된 형태라기 보다는 문제 상황에 좀더 유연하게 대처될 수 있다는 경험.

무엇을 상태로 저장해야 하는지를 파악해야 함.

어느 상황에서 dp를 생각해볼 수 있어야 하는지를 경험