BOJ: LIS 시리즈

2: https://www.acmicpc.net/problem/12015 3: https://www.acmicpc.net/problem/12738 4: https://www.acmicpc.net/problem/14002 5: https://www.acmicpc.net/problem/14003

  • 2월동안 187문제 풀기(지난달 누적 87개) (48/187)
  • 일단 2번과 3번은 쉽다. 그냥 LIS 풀듯이 풀면 된다.
  • 문제는 4번과 5번 출력을 해주어야 하는 부분이다.
    • 처음에는 어줍잖게 $O(NLogN)$으로 찾은 dp 배열을 이용해서 풀려고 했는데, 안일한 생각이었다.
    • 7 / 4 5 6 7 1 2 3 으로 입력이 들어오면 망한다.
    • 위의 예에서 LIS는 1 2 3 7일텐데 여기서 이미 망가져버린 1 2 34 5 6으로 되돌릴 계제가 없다.
    • 결국 다른 DP에서 복원할 때 하듯이, 중간 결과를 포인터로 저장해놓는 식으로 풀어야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

int N, x;
vector<int> lis;
vector<int> lisPos;
vector<int> nums;
vector<int> par;

int main() {
  scanf("%d", &N);
  par.resize(N);
  nums.reserve(N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &x);
    nums.push_back(x);
    auto it = lower_bound(lis.begin(), lis.end(), x);
    int n = it - lis.begin();
    par[i] = n != 0 ? lisPos[n - 1] : -1;
    if(it == lis.end()) {
      lis.push_back(x);
      lisPos.push_back(i);
    } else {
      *it = x;
      lisPos[n] = i;
    }
  }
  printf("%d\n", lis.size());
  int last = lisPos.back();
  vector<int> ans;
  while(last != -1) {
    ans.push_back(nums[last]);
    last = par[last];
  }
  reverse(ans.begin(), ans.end());
  for(int i : ans)
    printf("%d ", i);
}