BOJ 2568 - 전깃줄 - 2

문제

• LIS를 \(\text{O(n log n)}\)으로 구현하는 문제이다.
• 각 항의 정보는 a b로 주어지는데, a가 A 전봇대와의 연결 위치, b가 B 전봇대와의 연결 위치이다.
• a를 인덱스, b를 값으로 보면, LIS를 구성할 수 있는 하나의 경우의 a의 집합을 X라고 할 때, X의 여집합을 오름차순으로 출력해야 한다.

풀이

• LIS dp는 \(\text{O}( n^2 )\)이기 때문에, TLE가 난다.
• dp를 아래와 같이 정의하고, 이분 탐색을 사용해야 한다.
  • lis(i)=lis의 i 번째 항에 들어갈 수 잇는 b 위치의 최솟값
• 전깃줄 정보 ar을 a 기준으로 오름차순 정렬 후 순회하며 lis를 업데이트한다.
  • b가 \(k\)일 때, \(k \lt \text{lis(i)}\)를 만족하는 가장 작은 \(i\)를 이분 탐색으로 찾고, lis[i]를 \(k\)로 바꾼다.
    • lis[0...i-1]까지는 그대로 사용하고, lis[i]만 b가 \(k\)인 전깃줄을 사용하는 것이다.
  • 이때, 잘라야 하는 전깃줄을 출력해야 하기 때문에, 각 원소들의 lis에서의 위치 정보를 ari에 따로 저장한다.
    • ari의 사이즈는 n이고, 값의 범위는 [0, lis.size()-1]이 된다.
  • ari의 값을 역순으로 순회할 때, 처음 나오는 lis.size()-1, ..., 0들의 인덱스 집합을 I라고 하면, ar[I][0]가 서로 교차하지 않는 전깃줄들의 a 위치이다.
    • 정방향으로 순회할 때는 0, ..., lis.size()-1을 순서대로 찾으면 된다.

코드

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, aidx;
    cin >> n;
    vi lis, ari(n, 0);
    v<vi> ar(n, vi(2, 0));

    for (int i = 0; i < n; i++) {
        cin >> ar[i][0] >> ar[i][1];
    }
    sort(ar.begin(), ar.end());
    lis.push_back(0);
    ari[0] = 0;
    for (int i = 1; i < n; i++) {
        int cur = ar[i][1];
        if (ar[lis.back()][1] < cur) {
            lis.push_back(i);
            ari[i] = lis.size() - 1;
        } else {
            int s = -1, e = lis.size();
            while (s + 1 < e) {
                int mid = (s + e) / 2;
                if (ar[lis[mid]][1] <= cur)
                    s = mid;
                else
                    e = mid;
            }
            lis[e] = i;
            ari[i] = e;
        }
    }

    vi ans;
    aidx = lis.size() - 1;
    for (int i = ar.size() - 1; i >= 0; i--) {
        if (ari[i] == aidx) {
            ans.push_back(ar[i][0]);
            aidx--;
            if (aidx < 0) break;
        }
    }
    reverse(ans.begin(), ans.end());

    aidx = 0;
    ostringstream oss;
    oss << n - ans.size() << '\n';
    for (int i = 0; i < n; i++) {
        if (aidx < ans.size() && ar[i][0] == ans[aidx]) {
            aidx++;
            continue;
        }
        oss << ar[i][0] << '\n';
    }
    cout << oss.str();
    return 0;
}

풀고나서

• 이분 탐색 구현이 헷갈려, 직접 구현하며 되짚었다.
  그러던 중, 명확하게 정리한 글(이분 탐색(Binary Search) 헷갈리지 않게 구현하기)을 발견하고, 이해하는데 도움을 받았다.
  아래는 요약이다.
  • [lo, hi]가 Check(lo) != Check(hi)가 되도록 구간을 설정
    • 결정문제이기 때문에, T, ..., T, F, ..., F나 그 반대 등으로 설정
    • lo, hi는 항상 정답의 범위를 나타낼 수 있도록 해야합니다
      • lo를 출력해야 하는 문제의 답이 최대 n일 때 hi = n으로 선언하거나, hi를 출력해야 하는 문제의 답이 최소 0일 때 lo = 0으로 선언하면 안됩니다. (hi = n + 1, lo = -1로 선언해야 합니다)
  • while (lo + 1 < hi), mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid
  • 구한 경계에서 답이 lo인지 hi인지 생각해보고 출력
• 처음 제출은 96ms 정도가 나왔는데, 상위권은 32ms 정도인 것을 보고, 비교하며 차이점을 찾아내려 했다.
  • 처음에는 lis에 모든 전깃줄의 lis에서의 위치를 저장하려고, vector<stack<int>> 타입으로 선언했다.
    이게 문제라 생각해서 vector<int>로 바꾸고, ari를 따로 선언했지만, 시간이 유의미하게 달라지지 않았다.
  • 컴파일러가 최적화하겠지만, if…else보다 continue를 사용하는게 이론상 더 빠르다는 것을 알게 되었다.
  • 이분 탐색을 바로 실행하지 않고, lis.back()과 비교해서 더 크다면 바로 push_back하고, 아니면 탐색하는 방식으로 커팅이 가능하다.
  • ostringstream으로 출력도 최적화했지만, 시간이 달라지진 않았다.
  • 문제는 항상 넣던 sync_with_stdio, cin.tie 구문을 넣지 않은 것이었다…