| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 91 | 16 | 11 | 39.286% |
규진이는 $N$개의 별을 순서대로 관측하려고 한다. $i$번째로 관측할 별의 밝기는 $A_i$이다.
규진이는 반드시 관측 순서에 따라 별을 정확히 한 번씩 관찰해야 하고, 하루에 여러 개의 별을 관측할 수 있다. 또한, 하루 동안 관측한 별의 밝기 중 최댓값과 최솟값의 차이는 그날 관측한 별의 수 이하여야 한다.
규진이가 위 조건을 모두 만족하면서 모든 별을 관측하기 위해 필요한 최소 일수 $d$를 구해주자.
첫째 줄에 관측한 별의 개수 $N$이 주어진다. $(1 \le N \le 200\, 000)$
둘째 줄에 각 별의 밝기 $A_1, A_2, \ldots , A_N$ 이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$
모든 별을 관측하기 위해 필요한 최소 일수를 출력한다.
6 2 4 1 5 8 5
2
10 5 9 12 6 4 1 2 7 2 4
4
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2026. 01-02. K번