[BOJ 33922 // C++] 책 쌓기

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 33922번 문제인 책 쌓기이다.
문제는 아래 링크를 확인하자.

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

 

먼저, 주어진 책들을 가로가 세로 길이 이상인 방향으로 일괄적으로 돌려 생각해도 충분하다는 점을 관찰하자. 가로가 세로 길이 이상인 책 위에 세로가 가로 길이 이상인 책을 얹을 수 있다면 문제 제약에 의해 위의 책을 회전시킨 책도 올릴 수 있으며, 이것이 그 위로 새로 올릴 수 있는 책의 집합을 바꾸지 않기 때문이다.

 

주어진 책들의 몇몇 쌍에 대하여, 어떤 책을 다른 책 위에 올릴 수 있다는 관계가 성립하며, 이 관계는 poset을 이룬다. 따라서 이 문제는 이 책들의 집합의 poset에서의 최대 antichain의 크기를 구하는 것으로 해결할 수 있다. 같은 antichain에 속한 두 원소는 항상 서로 비교가 불가능해야 하므로, 책을 적절하게 뽑아 적절히 나열했을 때 가로의 길이가 strict하게 증가할 때 세로의 길이 또한 strict하게 증가하게끔 뽑을 수 있은 최대 책의 개수를 구하면 문제가 해결된다.

 

위의 문제는 LIS를 구하는 것으로 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int N, ans;
int A[200001];
pair<int, int> P[200001];

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

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> P[i].first >> P[i].second;
        if (P[i].first < P[i].second) swap(P[i].first, P[i].second);
    }
    sort(P + 1, P + N + 1, greater<>());
    memset(A, 0x3f, sizeof(A));
    A[0] = 0;
    for (int i = 1; i <= N; i++) {
        int L = 0, R = i;
        while (L < R) {
            int mid = (L + R) / 2 + 1;
            if (A[mid] >= P[i].second) R = mid - 1;
            else L = mid;
        }
        A[L + 1] = min(A[L + 1], P[i].second);
    }
    ans = N;
    while (A[ans] == 0x3f3f3f3f) ans--;
    cout << ans;
}