33922번 - 책 쌓기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 36 | 20 | 19 | 54.286% |
문제
$N$권의 책을 책상 위에 여러 무더기로 쌓아올리려고 한다. 책은 높이를 무시할 수 있는 직사각형 모양이며, $i$번째 책의 두 변의 길이는 $A_i$와 $B_i$이다. 책은 반드시 가로 방향, 세로 방향 중 하나와 나란한 방향으로 놓아야 한다. 즉, 각각의 책은 90도 회전할 수 있다. 또한, 한 무더기에 쌓아올려진 책을 밑에서부터 순서대로 봤을 때 가로 방향의 길이와 세로 방향의 길이가 각각 단조 감소해야 한다. 즉, 두 인접한 책의 가로 혹은 세로 방향의 길이가 같은 경우도 허용한다.
이 조건을 만족하는 방법 중에서 무더기의 개수가 최소가 되는 방법을 찾아라.
입력
첫째 줄에 책의 개수 $N$이 주어진다.
두번째 줄부터 이어지는 $N$개의 줄에 $A_i$와 $B_i$의 값이 공백으로 구분되어 주어진다.
출력
조건을 만족하며 책을 쌓는 방법 중 무더기의 최소 개수를 출력하여라.
제한
- 주어지는 수는 모두 정수이다.
- $1\leq N \leq 200\,000$
- $1 \le i \le N$ 인 각 $i$ 에 대하여: $1\leq A_i, B_i \leq 10^9$
예제 입력 1
5 1 5 4 2 3 3 3 4 5 2
예제 출력 1
3
첫 번째 무더기에 $5$번째 책과 $1$번째 책을 $(5, 2)$와 $(5, 1)$ 방향으로, 두 번째 무더기에 $4$번째 책과 $3$번째 책을 $(3, 4)$와 $(3, 3)$ 방향으로, 세 번째 무더기에 $2$번째 책을 놓으면 $3$개의 무더기로 책을 쌓는 것이 가능하다. 무더기를 더 적은 개수로 만드는 것은 불가능하다.
예제 입력 2
3 1 1 1 1 1 1
예제 출력 2
1