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

문제

가장 긴 증가하는 부분 수열 5 (https://www.acmicpc.net/problem/14003) 최대 100만 개의 원소를 가진 수열에서 LIS의 길이와 실제 수열을 출력하는 문제.

복잡도 분석

• time complexity : $O(N \log N)$
  • LIS 길이를 구하는 과정: $N \times \log N$
  • 역추적 과정: $N$
• space complexity : $O(N)$
  • 입력 배열, 위치 기록 배열(idx_v), LIS 끝값 관리용 벡터 각각 $N$.

접근법

단순히 LIS의 길이만 구하는 것을 넘어, 각 원소가 LIS의 몇 번째 위치(인덱스)에 기여했는지를 기록하는 것이 핵심임.

1. LIS 기록 및 위치 저장:
   • L 벡터를 이용해 $O(N \log N)$ LIS 로직을 수행함.
   • 각 원소 v[i]가 L의 어떤 인덱스에 들어가는지 idx_v[i]에 저장함.
2. 역추적(Backtracking):
   • L의 최종 크기가 $K$라면, 수열을 뒤에서부터 순회하며 idx_v[i]가 $K-1, K-2, \dots, 0$인 원소를 순차적으로 추출함.
   • 뒤에서부터 찾는 이유는 가장 최근에 갱신된(즉, 수열상 뒤에 있는) 유효한 원소를 안전하게 선택하기 위함임.

풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    vector<int> v(N), idx_v(N);
    for(int i = 0; i < N; i++) cin >> v[i];

    vector<int> L;
    for(int i = 0; i < N; i++) {
        if(L.empty() || L.back() < v[i]) {
            L.push_back(v[i]);
            idx_v[i] = L.size() - 1;
        } else {
            auto it = lower_bound(L.begin(), L.end(), v[i]);
            *it = v[i];
            idx_v[i] = distance(L.begin(), it);
        }
    }

    int LIS_len = L.size();
    cout << LIS_len << "\n";

    vector<int> res;
    int target_idx = LIS_len - 1;
    for(int i = N - 1; i >= 0; i--) {
        if(idx_v[i] == target_idx) {
            res.push_back(v[i]);
            target_idx--;
        }
    }

    reverse(res.begin(), res.end());
    for(int i = 0; i < res.size(); i++) {
        cout << res[i] << (i == res.size() - 1 ? "" : " ");
    }

    return 0;
}

이걸 어떻게 머리로 생각해내냐..;
14002번은 더 쉬운 문제로 dp로 풀고 역추적하면 되는것으로 보임.

Code Review

• 효율성: $N=10^6$에서 std::distance나 it - L.begin()은 $O(1)$이므로 성능에 지장이 없음.
• 역추적 논리: target_idx를 활용해 뒤에서부터 훑는 방식은 동일한 idx_v 값을 가진 원소들 중에서도 가장 적절한(뒤에 위치한) 원소를 선별해줌.
• 출력 최적화: reverse 후 한 번에 출력하여 출력 오버헤드를 줄임.

유사 문제 추천

• 가장 큰 증가하는 부분 수열 (BOJ 11055): LIS의 합을 구하는 문제 ($O(N^2)$ DP)
• 전깃줄 - 2 (BOJ 2568): LIS 응용 및 실제 원소 제외 처리
• 가장 긴 증가하는 부분 수열 4 (BOJ 14002): $N=1000$일 때 역추적 연습