백준 13397. 구간 나누기 2

tose33 2023. 2. 12. 10:58

13397번: 구간 나누기 2

첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수

www.acmicpc.net

mid를 구간의 점수의 최댓값의 최솟값으로 하고 이분 탐색한다.

그리고 해당 mid 값이 구간의 점수의 최댓값의 최솟값이 되려면 몇개의 구간으로 나누어야 하는지를 구한다.

나눠야 하는 구간에 따라 left, right를 조정한다.

8 3
1 5 4 6 2 1 3 7

구간의 점수의 최댓값 즉 mid=4 라면 구간이 몇개로 나뉘는지 보자.

{1,5,4} 까진 괜찮은데 {1,5,4,6}이 되면 6-1=5 이므로 6전에 구간을 나눠야한다. 이렇게 구간을 나눠보면

{1,5,4}, {6,2}, {1,3}, {7} 이런식으로 나뉜다.

즉 구간이 4 구간으로 나뉘는데 주어진 M=3이므로 불가하다.

따라서 구간이 덜 나뉘도록 mid 값을 조정해야 한다.