[14002] 가장 긴 증가하는 부분 수열 4 - c++

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

14002번: 가장 긴 증가하는 부분 수열 4

일단 예전에 풀었던 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 사용하는 것이라는 건 자명한 사실! 

하지만 여기선 추가 된것이 있었으니, 그 경로까지 구해야 하는 것이다.

이슈다 응용은 못한다....

일단 당연히 문제에 대해 고민을 해보고 답을 봤다.

---

풀이 아이디어

가장 긴 배열을 구하며 경로도 추가 적으로 pre 라는 배열에 저장한다.

사실 예전 이런 비슷한 문제를 풀었던 적이 있어 따로 배열에 저장해야겠다고 생각했으나 어떻게 이 문제에 적용시켜야 할지 몰랐다.

결국 난 몰랐던 거다.

 

가장 위의 인덱스 부터 내려오면서 연결리스트 구현 했던 방식으로 풀어내는 것을 보고 감탄했다...

 

말로만 하면 어려우니 코드를 보며 분석해보자

---

CODE

// 포도주 시식
#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n;
int a[1001], d[1001], pre[1001];

int main(){
  init();
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> a[i];

  for(int i = 1; i <= n; ++i){
    for(int j = 1; j < i; ++j){
      if(a[i] > a[j] && d[i] < d[j]+1){
        d[i] = d[j] + 1;
        pre[i] = j;
      }
    }
  }

  int maxi = 1, maxd = d[1];
  for(int i = 1; i <= n; ++i){
    if(maxd < d[i]){
      maxi = i;
      maxd = d[i];
    }
  }

  deque <int> ans;
  int cur = maxi;
  while(cur){
    ans.push_front(a[cur]);
    cur = pre[cur];
  }
  cout << ans.size() << '\n';
  for(auto x : ans) cout << x << ' ';  
  return 0;
}

 

1. 가장 긴 것을 찾으며 경로를 저장하는 로직

for(int i = 1; i <= n; ++i){
    for(int j = 1; j < i; ++j){
      if(a[i] > a[j] && d[i] < d[j]+1){
        d[i] = d[j] + 1;
        pre[i] = j;
      }
    }
  }

 

최대 값의 경로가 바로바로 저장된다.

input => 10 20 10 30 20 50
dp => 0 1 0 2 1 3 
pre => 0 1 0 2 1 4

위와 같은 식으로 저장된다.

 

2. 가장 긴 부분의 인덱스를 찾는다.

int maxi = 1, maxd = d[1];
  for(int i = 1; i <= n; ++i){
    if(maxd < d[i]){
      maxi = i;
      maxd = d[i];
    }
  }

maxi에 가장 긴 부분의 마지막 인덱스가 들어가게 된다

 

3. 경로를 따라가며 덱에 저장한다

deque <int> ans;
  int cur = maxi;
  while(cur){
    ans.push_front(a[cur]);
    cur = pre[cur];
  }

연결리스트 구현 할 때 했던 것과 똑같은 방식이다. pre배열의 저장된 값을 따라가다가 마지막 0이 나오면 멈추게 된다.

---

문제를 풀며

DP문제 정말 너무 어렵다. 실버 등급도 어려운데 골드 문제를 푸는 게 맞나 싶지만 할 수 있다고 생각하고 그렇게 믿고 싶었다. 하지만 답을 봐버렸다...

과연 이렇게 계속 풀어 나가는 것이 맞는지는 모르겠으나 정말 조금씩 감이 잡히기 시작하는 것 같다. 진짜 조금...

그렇다고 아직까지 나 스스로 답을 맞혀 보진 못했다 ㅎㅎ 

더 풀자..ㅜ 계속 풀자 ㅜ