[BOJ] 1400 - 가장 긴 증가하는 부분 수열 5

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

BOJ - 가장 긴 증가하는 부분 수열 5

문제 유형: LIS(Longest Increasing Subsequence), 다이나믹 프로그래밍, 이진 탐색

문제 난이도: Platinum V

시간 제한: 3초

메모리 제한: 512MB

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

풀이

n log n의 시간으로 실제 LIS를 만들기 위해서는, 역추적이 필요하다.

우선, 가짜 LIS를 담을 tails를 만든다. 실제 LIS는 아니다. 대신, tails에는 현재까지 appended된 최선의 값들이 들어 있다. 각각은 자신까지는 LIS가 맞다.

즉, tails의 마지막 숫자는 실제 lis의 꼬리가 된다.

append된 tails들의 기존 인덱스를 저장하기위해, tails_indices를 배열을 만든다.

역추적으로 실제 LIS를 복원하기위한 요소 간의 부모관계를 정의할 Parents를 만든다. 처음에는 모두 -1로 초기화한다. 각자가 루트가 된다고 보면 된다.

 

배열의 요소를 순차적으로 다음과 같이 다룬다:

  tails에서 lower_bound로 이진탐색하여 tails에서 arr[i]이상인 인덱스를 찾는다. 이를 pos라 하자.

  만약 pos의 값이 tails의 크기, 즉 arr[i]가 가장 크다면, LIS의 길이가 늘어난다. tails의 맨 뒤에 붙인다. 그러고 tails_indices의 맨 뒤에 인덱스를 붙인다.

  아니라면, tails에서 pos의 자리를 대체할 수 있다. tails[pos]와 tails_indices[pos]를 대체한다.

  아까 말했듯이, tails와 tails_indices의 끝은 특성상 실제 lis의 맨 끝이 붙어있다고 했다.

  즉, 이번에 pos에 추가된 수의 앞의 인덱스의 수가 자신의 이전의 수가 된다. parents[i] = tails_indices[pos-1]이 된다. pos가 0이면 자신이 루트이므로 아무 것도 하지않으면 된다.

 

위 반복을 마치면, 이제 복구할 차례이다. tails_indicies의 맨 끝에 실제 LIS의 맨 뒤 인덱스가 남아있다.

parent를 이용하여 역순으로 LIS를 복구해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> generateLIS(vector<int> &arr, int n) {
  if (n == 0)
    return {};
  vector<int> tails;
  vector<int> tails_indices;
  vector<int> parents(n, -1);

  for (int i = 0; i < n; ++i) {
    int pos = lower_bound(tails.begin(), tails.end(), arr[i]) - tails.begin();

    if (pos == tails.size()) {
      tails.push_back(arr[i]);
      tails_indices.push_back(i);
    } else {
      tails[pos] = arr[i];
      tails_indices[pos] = i;
    }

    if (pos != 0) {
      parents[i] = tails_indices[pos - 1];
    }
  }

  int lis_length = tails.size();
  vector<int> lis(lis_length);
  int k = tails_indices.back();

  for (int i = lis_length - 1; i >= 0; --i) {
    lis[i] = arr[k];
    k = parents[k];
  }

  return lis;
}

int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  vector<int> ans = generateLIS(arr, n);

  cout << ans.size() << "\n";
  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << " ";
  }
  cout << "\n";

  return 0;
}