1633 : 경로나누기
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 2 회
- 시도횟수
- 4 회
문제
농부 창호의 소들은 맛이 상당히 좋은 클로버들이 산마루에 일렬로 자라고 있는 것을 발견했다.
이 클로버들에게 물이 잘 공급되도록 하기 위해, 존은 스프링쿨러들을 설치하려고 한다.
설치를 쉽게 하기 위해, 이 스프링클러들은 각기 산마루에 일렬로 설치된다.
(쉽게 말해 길이L의 1차원 선분이라고 생각할 수 있다. 1≤L≤1,000,000이고 L은 짝수).
각 스프링클러는 설치된 위치에서 양 방향으로 정해진 거리만큼 물을 뿌린다.
이 거리는 정수 A..B 범위에 속하는데(1≤A≤B≤1000)이다.
창호는 모든 클로버들이 단 한 개의 스프링쿨러에만 물을 공급 받도록 하고 싶다.
또한, 창호는 물이 산마루의 양 끝을 넘는 범위에 뿌려지기 원치 않는다.
창호의 N마리(1≤N≤1000)소들은 각기 자신이 좋아하는 클로버들의 범위를 가지고 있다(서로의 선호하는 클로버 범위 구간들은 겹칠 수 있다).
이 범위는 닫혀있는 구간 (S,E)로 정의된다.
각 소들은 자신들이 좋아하는 범위 내의 클로버들에겐 한 개의 스프링클러에 의해서 물이 뿌려지기 원한다.
위 조건을 만족시키기 위해 필요한 최소의 스프링클러의 수를 구하시오.
입력형식
출력형식
입력 예2 8 1 2 6 7 3 6 |
출력 예3 |
Hint!
