Informatica Online Judge

  교차하지 않는 최대 현의 집합(Large) [1361 / 0551]

Time Limit(Test case) : 200(ms)
Number of users who solved : 22   Total Tried : 103


The Champion of this Problem (C++) : yeonhosuh1 - 0ms / 516byte
My Best Submission (C++) : N/A

[한국정보올림피아드 고등부 1996]

Background

평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로붙여져 있다.

이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력하는 프로그램을 작성하라.

Input

첫 번째줄은 주어지는 현의 개수 N이고, 다음의 N줄은 각 현의 양끝점의 번호가 주어진다.

[입력값의 정의역]
#Small Prob : N <= 10
#Large Prob : N <= 50

Output

구한 현의 개수를 출력한다.

IO Example

입력
5
97 31
1 45
27 5
11 65
43 72

출력
3

<설명> (5, 27), (97, 31), (72, 43)의 세 개의 현은 교차하지 않는다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]