벌목

면접 대비

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

요약

나무 각 구간의 무게와 운반 한계 W가 주어질 때, 각 조각이 W 이하가 되도록 나무를 자르는 최소 조각 수를 구합니다.

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

문제

집 앞에 있는 큰 나무를 치우려고 한다. 나무가 너무 커서 한 번에 다 들고 갈 수는 없다. 최대 $W$ 만큼의 무게를 들 수 있다면, 나무를 몇 조각으로 잘라야 하는가?

나무에는 땅에 연결된 줄기가 하나 있고, 줄기는 여러 개의 가지로 갈라질 수 있다. 가지도 다시 갈라질 수 있다. 나무의 각 구간은 끊기지 않은 나무 덩어리이며, 여러 가지로 갈라질 수도 있고 그렇지 않을 수도 있다.

나무의 어느 지점에서든 자를 수 있다. 구간의 시작점, 끝점, 중간 어디든 가능하다. 가지가 갈라지는 지점은 아주 작은 부분으로 본다. 가지가 갈라지기 직전이나 직후에 잘라도 원래 가지의 무게는 늘지 않는다. 다만 이 선택에 따라 하위 가지들이 한 덩어리로 잘리는지, 아니면 가지 하나만 따로 잘리는지가 정해진다.

입력

첫 줄에 운반 능력 $W$ 가 주어진다. 다음 줄부터 첫 번째 나무 구간, 즉 줄기의 설명이 이어진다.

구간은 재귀적으로 정의된다. 첫 줄에는 구간의 무게 $M$ 과 이 구간 끝에서 뻗어 나오는 가지의 개수 $N$ 이 주어진다. 이어서 $N$ 개의 가지 구간 설명이 차례로 나온다.

출력

나무를 잘라야 하는 조각의 개수를 한 개의 수로 출력한다.

제한

$1 \leq W, M \leq 10^9$
$0 \leq N \leq 10^5$
모든 나무 구간의 무게 합은 $10^9$ 를 넘지 않는다.
구간의 총 개수는 $10^5$ 를 넘지 않는다.

힌트

그림은 예제 테스트 케이스에 대해 가능한 해 몇 가지를 보여준다.

예제3

예제 1
입력
```
1
10 0
```
예상 출력
```
10
```
예제 2
입력
```
7
5 2
7 0
2 0
```
예상 출력
```
2
```
예제 3
입력
```
5
2 3
2 2
1 0
1 0
6 0
4 2
3 0
2 0
```
예상 출력
```
5
```