C++ 백준 1149 (RGB거리)

백준 1149 (RGB거리)

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

1149번: RGB거리

---

전형적인 DP문제이다.

 

설명

---

문제를 보면 다음단계의 집색깔은 전단계의 집색깔과 같을 수 없다.

한단계 한단계 나아가며 현재단계에서의 optimal solution은 전단계의 optimal solution과 관계가 있다.

이 말은 dynamic programming을 통해 이문제를 해결할 수 있다는 것이다.

예를 들면 현재 네번째 집의 색이 R이라면 세번째 집의 색이 G 또는 B였던 dp값의 최소를 가져다가 쓰면 된다는 것이다.

 

즉, dp[i][j](i는 현재 몇번째인지, j는 집의 색깔)는 현재 i번째에 j색의 집을 놓았을 경우 지금까지 든 최소비용을 뜻한다.

 

코드를 보며 이해해보자

구현

---

#include <iostream>
#include <algorithm>
#define MAX 1000*1000+1
using namespace std;

int dp[1001][3];
int cost[1001][3];
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;
	cin>>n;
	int r,g,b;
    for(int i=1;i<=n;i++){
        cin>>r>>g>>b;
        cost[i][0]=r;
        cost[i][1]=g;
        cost[i][2]=b;
    }
    dp[1][0]=cost[1][0];
    dp[1][1]=cost[1][1];
    dp[1][2]=cost[1][2];
    
	for(int i=2;i<=n;i++){
            dp[i][0] = min(dp[i-1][1],dp[i-1][2])+cost[i][0];
            dp[i][1] = min(dp[i-1][0],dp[i-1][2])+cost[i][1];
            dp[i][2] = min(dp[i-1][1],dp[i-1][0])+cost[i][2];
    }
	int minimum = MAX;
	for (int i = 0;i <= 2;i++) {
		minimum = min(minimum, dp[n][i]);
	}
	cout<<minimum;
	return 0;
}

결국 dp[n][빨강], dp[n][초록], dp[n][파랑] (n번째 집이 해당 색일 때 지금까지 최소비용)중 가장 작은 값이 답이되는 것이다.

 

 

DP문제의 특성상 생각하기 까지는 난이도가 있지만, 구현은 점화식만 쓰면 되기때문에 매우 쉽다.