백준 14003번 가장 긴 증가하는 부분 수열 5[C++]

1. 문제 풀이

 lower_bound, 즉 이분 탐색을 사용하여 풀이하였습니다. 각 배열에 값이 증가하는 부분 수열에서 어느 위치에 존재하는가를 저장하는 방법을 통해 풀이할 수 있습니다. 증가하는 부분 수열은 항상 오름차순으로 정렬이 되어있기 때문에 lower_bound로 각 배열의 값이 위치할 수 있는 곳을 알아낼 수 있습니다. 만약, 부분 수열 내 값보다 배열의 값이 크다면 부분 수열의 크기를 증가하고 추가하면 되고 아니라면 해당 위치에 배열의 값을 삽입합니다. 그리고 배열의 값이 부분 수열에서 위치하는 인덱스 정보를 따로 저장하여 처리합니다. 모든 과정이 끝나게 되면 부분 수열의 길이가 LIS의 길이가 됩니다. 그리고 배열의 각 값마다 LIS에서 위치할 수 있는 정보를 바탕으로 역추적하여 LIS의 원소값을 알 수 있습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
int a[1'000'005];
int pos[1'000'005];
vector<int> lis;

int main() {
  fastio(nullptr, false);

  // input
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];  

  // solve
  for(int i = 0; i < n; i++){
    int idx = lower_bound(all(lis), a[i]) - lis.begin();
    
    if(idx == sz(lis)) lis.pb(a[i]);
    else lis[idx] = a[i];
    
    pos[i] = idx;
  }
  
  vi ans;
  int cx = max_element(pos, pos+n) - pos;
  int cy = pos[cx];
  
  ans.pb(a[cx]);
  while(cy > 0){
    for(int nx = cx; nx >= 0; nx--){
      if(pos[nx] == cy - 1 && a[cx] > a[nx]){
        ans.pb(a[nx]);
        cy--;
        cx = nx;
        break;
      }
    }
  }

  // output
  cout << sz(ans) << nl;
  for(auto it = ans.rbegin(); it < ans.rend(); it++) cout << *it << ' ';
}

 

3. 제출 결과