페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1769

교차하지 않는 원의 현들의 최대집합 1초 - MB

문제

평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력하는 프로그램을 작성하라. 단, 1≤N≤50이고, 주어진 각 점은 많아야 한 현의 끝점이 될 수 있다.


입력

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


출력

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


예제1

입력
5

9731
145
275
1165
4372
출력
3


태그


출처

KOI 전국 1996 고2

역링크