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

문제

• 크기가 \(N(1 \le N \le 32000)\)인 수열 \(A(-1000000000\le A_i \le 10000000000)\)이 주어진다.
• 수열 \(A\)의 LIS의 길이와, 정답이 될 수 있는 LIS 중 하나를 출력해야 한다.

풀이

• Binary search를 사용한 O(nlogn)의 LIS 풀이를 사용했다.

코드

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
#define v vector

using namespace std;
using vi = vector<int>;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, lidx;
    cin >> n;
    vi ar(n, 0), lis, ari(n, 0);
    for (int i = 0; i < n; i++)
        cin >> ar[i];
    lis.push_back(ar[0]);
    for (int i = 1; i < n; i++) {
        if (lis.back() < ar[i]) {
            lis.push_back(ar[i]);
            ari[i] = lis.size() - 1;
            continue;
        }
        int ci = upper_bound(lis.begin(), lis.end(), ar[i]) - lis.begin();
        if (ci > 0 && lis[ci - 1] == ar[i]) {
            ari[i] = ci - 1;
            continue;
        }
        lis[ci] = ar[i];
        ari[i] = ci;
    }
    cout << lis.size() << endl;
    lidx = lis.size() - 1;
    stack<int> res;
    for (int i = n - 1; i >= 0; i--) {
        if (ari[i] == lidx) {
            res.push(ar[i]);
            lidx--;
            if (lidx == -1) break;
        }
    }
    while (!res.empty()) {
        cout << res.top() << ' ';
        res.pop();
    }
    return 0;
}

풀고나서

• 처음 AC를 받는 코드는 204ms가 걸렸다. 다른 사람들의 풀이를 보고 아래와 같이 적당하게 이상적인 풀이까지 시간을 줄여보았다.

방법	메모리	시간
기존	18220KB	204ms
방법 1	18220KB	192ms
방법 2	18220KB	184ms

• 방법 1 : if…else를 if-continue로 바꿨다.
  • 이전에는 미세하게 차이가 나서 확신하지 못했는데, 이번에도 바꾸면서 효과를 봐서, 확실히 성능 차이가 있다는 것을 알게 되었다.
• 방법 2 : LIS의 마지막 원소로 추가하는 경우가 upper_bound 구문보다 먼저 실행되게 커팅했다.