목줄에 묶인 소

면접 대비

시간 제한2초메모리 제한512 MB

요약

N개의 구간이 주어질 때, 모든 구간이 선택한 점을 하나 이상 포함하도록 하는 반정수 절단점의 최소 개수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 구간, 정렬
정답자: 아직 제출이 없습니다

문제

농부 존이 소 $N$ 마리를 목줄로 말뚝에 묶어 두었다. 말뚝은 동서로 뻗은 울타리 옆 정수 위치에 박혀 있고, 울타리 길이는 5,300,000미터를 넘지 않는다. 소는 저마다 목줄을 동쪽으로 끝까지 당기고 있지만 울타리 끝을 넘어가지는 않는다. 말뚝 위치가 $s$ 이고 길이가 $l$ 인 목줄은 울타리 위에서 $s$ 부터 $s+l$ 까지를 차지한다.

존의 아내는 목줄을 야만적이라고 여겨 무딘 식칼을 들고 울타리로 왔다. 칼로 자를 수 있는 횟수가 얼마 없어서 되도록 적게 자르려고 한다. 한 번 자를 때는 이웃한 두 정수 위치의 한가운데, 즉 $x+0.5$ 지점에 서서 눈앞을 지나는 목줄을 모두 끊는다. 말뚝 위치가 $s$ 이고 길이가 $l$ 인 목줄은 $s \le x$ 이고 $x+1 \le s+l$ 일 때 $x+0.5$ 에서 끊긴다.

목줄마다 말뚝 위치와 길이가 주어진다. 소를 모두 풀어 주려면 최소 몇 번 잘라야 하는지 구하라.

입력

첫째 줄에 소의 수 $N$ 이 주어진다. ( $1 \le N \le 32000$ )

다음 $N$ 개 줄에는 목줄 하나를 나타내는 두 정수가 공백으로 구분되어 주어진다. 첫 번째 정수는 말뚝의 위치, 두 번째 정수는 목줄의 길이다. 두 값 모두 양의 정수이고, 말뚝 위치와 목줄 길이의 합은 5,300,000 이하다.

출력

모든 목줄을 한 번 이상 끊는 데 필요한 최소 절단 횟수를 한 줄에 출력한다.

힌트

다음 그림은 목줄 일곱 개가 놓인 모습을 나타낸다. 위쪽 두 줄은 울타리 위의 정수 위치다.

                  1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3
-------------------------
. 111111111 . . . . . . .
. . . 222222222222222 . .
. . 3333333 . . . . . . .
. . . . 4444444 . . . . .
. . . . . . . . 555555555
66666666666 . . . . . . .
. . . . . . 7777777 . . .

$5.5$ 에서 자르면 목줄 1, 2, 3, 4, 6이 끊어진다. $9.5$ 에서 한 번 더 자르면 목줄 5와 7이 끊어진다. 다른 위치를 골라도 되지만, 목줄 5와 6을 한 번에 끊는 지점은 없으므로 적어도 두 번은 잘라야 한다.

예제4

예제 1
입력
```
7
2 4
4 7
3 3
5 3
9 4
1 5
7 3
```
예상 출력
```
2
```
예제 2
입력
```
1
1 1
```
예상 출력
```
1
```
예제 3
입력
```
5
1 2
3 2
5 2
7 2
9 2
```
예상 출력
```
5
```
예제 4
입력
```
4
1 10
3 5
5 2
2 8
```
예상 출력
```
1
```