[BOJ] 1149_RGB거리

RGB거리

문제 링크: https://www.acmicpc.net/problem/1149

1149번: RGB거리

이 문제는 Dynamic Programming 문제이다.
하나의 선택을 했을 경우 다음의 선택에서는 두 개의 선택지로 나뉘어진다.
우리는 가장 최솟값을 구해야한다.
그 두 개의 선택지 중 더 작은 값을 고르면 된다.

 

하지만 반대로 내가 하나의 선택을 했다면, 이전에 걸어왔던 선택지에서 현재 내가 선택한 색상을 제외한 나머지를 선택할 수 있다.

 

만일 현재 내가 r를 선택했다면, 이전에 g 또는 b를 골랐던 선택지를 가져온다.
똑같이 현재 내가 g를 선택했다면, 이전에 r 또는 b를 골랐던 선택지를 가져온다.
b도 동일하게 ,r 또는 g를 골랐던 선택지를 가져온다.

 

이제 두 개의 선택지 중 더 작은 값들을 가져온다.
그렇게 한다면, 현재의 선택에서 가장 작은 값들을 유추할 수 있다.

 

마지막까지 간 후 마지막의 선택에서 가장 작은 선택지를 고르면 된다.

 

• 정답코드

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
  
    int main() {
        int n;
        cin >> n;
        int dp[3] = { 0, };
  
        while (n--) {
            int r, g, b;
            cin >> r >> g >> b;
            int temp[3] = { 0, };
            temp[0] = r + min(dp[1], dp[2]); //이전에 r를 제외한 g 또는 b를 선택
            temp[1] = g + min(dp[0], dp[2]);//이전에 g를 제외한 r 또는 b를 선택
            temp[2] = b + min(dp[0], dp[1]);//이전에 b를 제외한 r 또는 g를 선택
            dp[0] = temp[0]; //이번에 r 선택
            dp[1] = temp[1]; //이번에 g 선택
            dp[2] = temp[2]; //이번에 b 선택
        }
  
        cout << min(dp[0] , min(dp[1], dp[2])) << endl;
        return 0;
    }

---

 

ps. 원래 이 문제를 혼자서 해결하지 못하였다.
내 첫 걸음은 rgb 각각의 색상에 플래그를 세워준 것이다.
이전에 빨간색을 골랐다면 이전에 고른 플래그와 비교하여 빨간색 이외의 색상을 고르게 한다.
초롱 파랑도 동일하다.
해당 색상 이외의 값 중 더 작은 값들을 고르면 최솟값이라 생각을 했다.
하지만 이 경우 현재의 최선의 선택만 할 뿐 전체 흐름에서 최고의 선택이 되지 않는다.
내 코드는 이 부분에서 틀린 답이 나왔음을 이해하고 처음부터 다시 시작했다.

• 이전코드

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
  
    class RGB {
    public:
        int rgb[3];
        //int R;
        //int G;
        //int B;
        int flag[3];
        RGB(int r, int g, int b) {
            /*R(r),G(g),B(b){}*/
            rgb[0] = r;
            rgb[1] = g;
            rgb[2] = b;
            if (r < g) {
                if (r < b) {// r<b,g
                    flag[0] = 0;
                    if (b < g) {
                        //r<b<g
                        flag[1] = 2;
                        flag[2] = 1;
                    }
                    else {
                        //r<g<b
                        flag[1] = 1;
                        flag[2] = 2;
                    }
                }
                else {//b < r < g
                    flag[0] = 2;
                    flag[1] = 0;
                    flag[2] = 1;
                }
            }
            else {
                if (g < b) {// g<b,r
                    flag[0] = 1;
                    if (b < r) {
                        //g<b<r
                        flag[1] = 2;
                        flag[2] = 0;
                    }
                    else {
                        //g<r<b
                        flag[1] = 0;
                        flag[2] = 2;
                    }
                }
                else { // b<g<r
                    flag[0] = 2;
                    flag[1] = 1;
                    flag[2] = 0;
                }
            }
        }
    };
  
    class card {
    public:
        int a;
        int b;
        int m;
        bool flag;
        card(int a_,int b_) {
            a = a_;
            b = b_; 
            m = min(a, b);
            if (a < b) {
                flag = true;
                m = a;
            }
            else {
                flag = false;
                m = b;
            }
        }
    };
    int findIdx(vector<RGB*>list) {
        int idx = 0;
        int min = 50000000;
        for (int i = 0; i < list.size(); i++)
            if (min > list[i]->rgb[list[i]->flag[0]]) {
                min = list[i]->rgb[list[i]->flag[0]];
                idx = i;
            }
        return idx;
    }
  
  int main() {
      int n;
      cin >> n;
      vector<RGB*> list;
      for (int i = 0; i < n; i++) {
          int arr[3];
          for (int k = 0; k < 3; k++)
              cin >> arr[k];
          list.push_back(new RGB(arr[0], arr[1], arr[2]));
      }
  
      int minIdx =0;
      int count = list[minIdx]->rgb[list[minIdx]->flag[0]];
      int flag = list[minIdx]->flag[0];
      RGB* temp;
      for (int i = minIdx - 1; i >= 0; i--) {
          for (int k = 0; k < 3; k++) {
              temp = list[i];
              if (flag != temp->flag[k]) {
                  count += temp->rgb[temp->flag[k]];
                  flag = temp->flag[k];
                  break;
              }
          }
      }
      flag = list[minIdx]->flag[0];
      for (int i = minIdx+1; i < n; i++) {
          for (int k = 0; k < 3; k++) {
              temp = list[i];
              if (flag != temp->flag[k]) {
                  count += temp->rgb[temp->flag[k]];
                  flag = temp->flag[k];
                  break;
              }
          }
      }
      cout << count << endl;
  
      return 0;
  }