시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 608 | 111 | 67 | 16.750% |
홍준이는 한국에서 손에 꼽히는 부자 중 한 명이다. 홍준이의 집은 N개의 방이 원형으로 나열된 형식으로 구성되어 있다. 홍준이는 자신의 집에 K개의 감시 카메라를 설치했다. 각 감시 카메라는 원형으로 나열된 방들 중 일부 연속된 구간을 감시한다. 홍준이는 모든 방을 다 감시하고 싶어 하는데, 이미 설치된 K개의 감시 카메라 중 몇 개는 필요하지 않다는 것을 깨달았다.
홍준이의 방은 1번 방부터 N번 방까지 원형으로 배열되어 있다. 즉, 1번 방 양 옆에는 2번 방과 N번 방이 있고, N번 방 양 옆에는 N-1번 방과 1번 방이 있다.
K개의 감시 카메라가 감시하는 구간에 대한 정보가 주어졌을 때, 모든 방을 감시하기 위해 필요한 최소 감시 카메라 개수를 구하는 프로그램을 작성하시오.
첫 줄에 방의 개수 N과 감시 카메라의 개수 K가 주어진다. (3 ≤ N ≤ 106, 1 ≤ K ≤ 106)
다음 K개의 줄에 각 감시 카메라에 대한 정보 ai와 bi가 주어진다. (1 ≤ ai, bi, ≤ N)
ai ≤ bi 인 경우, ai ≤ j ≤ bi 를 만족하는 j번 방이 감시 받는다는 것을 의미하고, ai > bi 인 경우, 1 ≤ j ≤ bi 혹은 ai ≤ j ≤ N 을 만족하는 j번 방이 감시 받는다는 것을 의미한다.
홍준이가 모든 방을 감시하기 위해 필요한 감시 카메라의 최소 개수를 출력한다. 만약, 모든 방을 감시하는 것이 불가능하다면, impossible
을 출력한다.
100 7 1 50 50 70 70 90 90 40 20 60 60 80 80 20
3