C++ 백준 17404 (RGB거리 2)

백준 17404 (RGB거리 2)

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

17404번: RGB거리 2

---

이 문제는 백준 1149(RGB거리)의 응용버전이다.

1149번 RGB거리에 대한 설명은 여기(링크)에 있으니 DP관점의 해결방법을 알고오자.

 

기존 1149번(이하 RGB거리1)문제와 달리 하나의 조건이 추가되었다.

처음집과 마지막집의 색이 달라야 한다는 것이다.

RGB거리1에서는 처음과 마지막은 고려하지 않았기 때문에 한번의 DP과정을 통해 해결할 수 있었다.

 

처음과 마지막이 같지 않으려면 어떻게 해야할까?

둘중에 하나를 고정시켜놓고 돌려보면 된다.

구현의 편의상, 그리고 DP의 특성상 처음을 고정시켜야 한다.

즉, 처음집이 R,G,B일때 각각 RGB거리1때 한 과정을 돌려보면 총 9가지경우의 수가 생길것이다.

 

1. 1번집이 R이고 마지막집이 R일때 최소비용

2. 1번집이 R이고 마지막집이 G일때 최소비용

3. 1번집이 R이고 마지막집이 B일때 최소비용

4. 1번집이 G이고 마지막집이 R일때 최소비용

5. 1번집이 G이고 마지막집이 G일때 최소비용

6. 1번집이 G이고 마지막집이 B일때 최소비용

7. 1번집이 B이고 마지막집이 R일때 최소비용

8. 1번집이 B이고 마지막집이 G일때 최소비용

9. 1번집이 B이고 마지막집이 B일때 최소비용

 

처음과 마지막집은 색이 같으면 안되므로 1, 5, 9번을 제외한 나머지 중에서 최소값을 찾으면 답이다.

 

구현

---

#include <iostream>
#include <algorithm>
#define MAX 1000*1000+1
using namespace std;
int cost[1001][3];
int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
    int ans = MAX;
    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;
    }
    
    for(int start=0; start<=2; start++){
        int dp[1001][3];
        for(int j=0;j<=2;j++){
            if(j==start) dp[1][start]=cost[1][start];
            else dp[1][j]= MAX;
        }
        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];
        }
        for(int j=0;j<=2;j++){
            if(j==start) continue;
            ans = min(ans, dp[n][j]);
        }
    }
    cout<<ans;
    return 0;
}

 

 

RGB거리1과 마찬가지로 DP문제의 특성상 점화식을 뽑기까지는 난이도가 있지만, 구현은 쉽다.