관측 시간표
문제
한 천문대에는 망원경이 한 대뿐이다. 이 망원경을 쓰려는 연구자들이 관측 신청서를 N장 냈고, 신청서마다 관측을 시작하는 시점과 끝내는 시점이 정수로 적혀 있다.
망원경이 한 대이므로 두 관측을 같은 시간에 진행할 수는 없다. 다만 한 관측이 끝나는 시점에 다른 관측을 시작하는 것은 된다. 망원경을 옮기거나 식히는 시간은 없다고 가정한다. 신청서에 적힌 시점은 바꿀 수 없으므로, 어떤 신청을 받아들이려면 적힌 시점 그대로 진행해야 한다. 시작 시점과 끝내는 시점이 같은 신청서도 있는데, 이런 관측은 시간을 전혀 쓰지 않는다.
천문대 담당자는 받아들이는 신청서의 수를 최대로 하고 싶다. N장의 신청서가 주어졌을 때, 서로 겹치지 않게 진행할 수 있는 관측의 최대 개수를 구하는 프로그램을 작성하여라.
예를 들어 N=11장의 신청서가 다음의 표와 같다고 해보자.
| 신청서 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 시작 시점 | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| 끝내는 시점 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
이때 1번, 4번, 8번, 11번 신청서를 받아들이면 네 관측이 서로 겹치지 않는다.
| 받아들인 신청서 | 1 | 4 | 8 | 11 |
|---|---|---|---|---|
| 시작 시점 | 1 | 5 | 8 | 12 |
| 끝내는 시점 | 4 | 7 | 11 | 14 |
1번 관측이 4에 끝나고 4번 관측이 5에 시작하며, 4번이 7에 끝나고 8번이 8에 시작하고, 8번이 11에 끝나고 11번이 12에 시작한다. 어느 두 관측도 시간이 겹치지 않는다.
다섯 장을 고르는 방법은 없다. 이 예시에서는 어느 신청서든 2 이상의 시간을 쓰고 가장 빨리 끝나는 것도 4에 끝나므로, 다섯 장을 이어 붙이면 마지막 관측이 12보다 이르게 끝날 수 없다. 끝내는 시점이 12 이상인 신청서는 9번과 10번과 11번뿐이고, 그 가운데 어느 것을 마지막에 두어도 그 앞에 네 장을 이어 붙일 수 없다. 따라서 현재 예시에서 정답은 4다.
입출력 예시
예시 1
입력
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
출력
4
예시 2
입력
5 679 684 63 97 496 530 23 66 448 492
출력
4
예시 3
입력
1 292 314
출력
1
입력 조건
가장 먼저 신청서의 수 N이 첫째 줄에 주어진다. N은 1 이상 100,000 이하의 자연수다.
이어서 둘째 줄부터 N+1번째 줄까지 신청서가 한 줄에 하나씩 주어진다. 각 줄에는 관측을 시작하는 시점과 끝내는 시점이 공백 하나로 구분되어 차례대로 주어진다. 두 시점은 모두 0 이상 1,000,000,000 이하의 정수이며, 시작 시점은 끝내는 시점보다 작거나 같다.
출력 조건
서로 겹치지 않게 진행할 수 있는 관측의 최대 개수를 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 한 관측이 끝나는 시점에 다른 관측을 시작하는 것은 됩니다
- 시작 시점과 끝내는 시점이 같은 신청서도 주어집니다. 이런 관측은 시간을 쓰지 않으므로 같은 시점에 끝나는 다른 관측과 함께 받아들일 수 있습니다
- 신청서에 적힌 시점은 바꿀 수 없습니다. 받아들인 관측은 적힌 시점 그대로 진행합니다
- N이 100,000까지 올라가므로 신청서의 모든 부분집합을 확인하는 방법으로는 시간 안에 끝나지 않습니다
- 출력은 수 하나와 줄바꿈뿐입니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
1 292 314
1
5 679 684 63 97 496 530 23 66 448 492
4
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
4
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.