건초 더미 탑

면접 대비

시간 제한1초메모리 제한128 MB

요약

너비와 너비, 너비와 폭이 모두 다른 지푸라기 최대 20개가 주어질 때, 아래에 놓인 것이 위에 놓인 것보다 너비와 폭이 모두 엄격히 큰 조건을 만족하는 가장 긴 사슬의 길이를 구한다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 정렬, 배열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

소들이 새로운 놀이를 만들었다. 한 소가 창고에서 건초 더미 $N$ 개( $3 \le N \le 20$ )를 꺼내 온다. 각 건초 더미의 높이는 모두 $1$ 이며, 가로 길이와 세로 길이는 각각 서로 다른(고유한) 값을 가진다.

두 번째 소는 건초 더미 몇 개를 골라 탑을 쌓는다. 어떤 건초 더미를 다른 건초 더미 위에 올리려면, 아래에 있는 건초 더미의 가로와 세로가 위에 있는 건초 더미의 가로와 세로보다 모두 엄격히 커야 한다. 건초 더미는 회전할 수 없으므로 가로와 세로를 서로 바꿀 수 없다.

규칙에 맞게 쌓을 수 있는 가장 높은 탑의 높이를 구하여라. 모든 건초 더미의 높이가 $1$ 이므로, 탑의 높이는 사용한 건초 더미의 개수와 같다.

입력

첫째 줄: 정수 $N$ 하나.
둘째 줄부터 $N+1$ 번째 줄까지: 각 줄에 건초 더미 하나의 가로 길이와 세로 길이가 공백으로 구분되어 주어진다.

출력

첫째 줄: 규칙에 맞게 쌓을 수 있는 가장 높은 탑의 높이.

힌트

예제에서는 여섯 개의 건초 더미 중 다섯 개를 골라 높이 $5$ 의 탑을 쌓을 수 있으며, 같은 높이의 탑을 만드는 다른 방법도 존재한다.

예제1

예제 1
입력
```
6
6 9
10 12
9 11
8 10
7 8
5 3
```
예상 출력
```
5
```