안녕하세요,
재재입니다.
BOJ 1666 최대 증가 직사각형 집합 문제 풀이 입니다.
BOJ 1666 최대 증가 직사각형 집합
(1) 문제 설명
분류 : graph, segment tree
출처 : https://www.acmicpc.net/problem/1666
N개의 직사각형이 좌표 위에 흩어져 있고 이 중 몇 개의 직사각형을 선택하여 집합 L을 구성하려 합니다.
왼쪽 아래의 점을 시작점, 오른쪽 위의 점을 끝점이라고 정의 할 때,
집합의 임의의 두 원소 p, q에 대하여 p의 끝점 x좌표가 q의 시작점 x좌표보다 작고,
마찬가지로 y좌표도 작거나 또는 q의 끝점 x좌표가 p의 시작점 x좌표보다 작고 y좌표 역시 작아야 합니다.
문제는 위의 조건을 만족하는 집합의 최대 원소 개수를 구하는 것입니다.
(2) 풀이 도출
바로 LIS를 사용해서 문제를 풀이하는데에는 어려움이 있습니다.
\( (x_b, y_b) \) ~ \( (x_t, y_t) \) 에서 어떤 친구를 다음 친구로 갖는 게 이득 인지에 대한 정보를 확신 할 수 없습니다.
그래서 접근은 segment tree 를 활용하는 게 좋아보입니다.
또한 이 tree 는 x보다 작고 y보다 작은 것의 쿼리를 구할 수 있어야하며,
\( (x_b, y_b) \) 의 좌측 아래로 쿼리를 날리고, 업데이트는 \( (x_t, y_t) \)에 해야합니다.
BOJ 1666 최대 증가 직사각형 집합