서로 교차하지 않는 원의 현 최대 개수
면접 대비시간 제한1초메모리 제한128 MB
원 위 100개의 점에 놓인 최대 50개의 현 중에서 서로 교차하지 않는 현을 최대 몇 개 고를 수 있는지 구합니다.
문제
원 둘레에 100개의 점이 같은 간격으로 놓여 있으며, 시계 방향으로 1부터 100까지 번호가 붙어 있다. 이 점들을 양끝점으로 하는 N개의 선분(현)이 주어진다. 주어진 현들 중에서 서로 교차하지 않도록 고를 수 있는 현의 최대 개수를 구하라.
단, 1 ≤ N ≤ 50이며, 각 점은 최대 하나의 현의 끝점으로만 등장한다.
입력
첫째 줄에 현의 개수 N이 주어진다. 다음 N개의 줄에는 각 현의 두 끝점 번호가 한 줄에 하나씩 주어진다.
출력
서로 교차하지 않게 고를 수 있는 현의 최대 개수를 출력한다.
힌트
추가 힌트는 없다.