(14003) 가장 긴 증가하는 부분 수열 5

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

단계별로 풀어보기

32단계(동적 계획법과 최단거리 역추적) 3번째

 

 

 

간혹 dp 갱신 방법에 따라 from배열로는 해결하지 못하는 경우가 있다.

이 문제에서는 from대신 자신이 LIS에서 몇 번째 원소인지 알려주는 lis배열을 추가하였다.

역추적할 땐 LIS의 크기 x를 선언하고 list배열을 거꾸로 탐색하면서, 지금 원소가 LIS 배열의 x번째 원소가 맞는지 확인한다. 맞다면 현재 수는 x번째 원소이고, 이제 x-1번째 원소를 찾아야 하므로 x의 값을 1 줄인다. 1번째 원소를 찾았다면 LIS를 구성하는 수를 전부 찾았으므로 종료한다(편의를 위해 1-based 인덱싱으로 설명하였으나 실제 코드에서는 0-based 인덱싱으로 작성하여 차이가 조금 있다).

 

인터넷에서 가장 많이 보이는 방법이자 예전 계정에서 푼 방법은 이분 탐색을 직접 구현해 from배열을 저장할 수 있도록 만든 코드였는데, 이 방법이 더 쉬운 것 같다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n), ans, lis(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  for(int i=0;i<n;i++){
    int idx= lower_bound(ans.begin(), ans.end(), v[i])-ans.begin();
    
    if(idx==ans.size()){
      ans.push_back(v[i]);
      lis[i]= ans.size()-1;
    }else{
      ans[idx]= v[i];
      lis[i]= idx;
    }
  }
  
  cout << ans.size() << "\n";
  for(int i=0;i<n;i++) cout << lis[i] << " ";cout<<"\n";
  
  vector<int> res;
  int x= ans.size()-1;
  
  for(int i=n-1;x>=0;i--){
    if(lis[i]==x){
      res.push_back(v[i]);
      x--;
    }
  }
  
  for(int i=res.size()-1;i>=0;i--)  cout << res[i] << " ";
  
  return 0;
}