(백준) 구간나누기2 _ 13397

https://www.acmicpc.net/problem/13397

 

🐢 설명

처음에는 좀 막막하게 다가온 문제이다. N개의 수가 주어졌을 때 어느 구간으로 나눴을 때 구간 내 최대값의 차이가 최소인 수를 구하는 문제이다.

 

구간의 크기를 동적으로 바꿔줘야 하는 문제인가 했지만 이분탐색으로 풀 수 있는 문제였다. 그럼 뭘 이분탐색할지가 중요한데 바로 구간 내 값의 차이를 이분탐색하면 된다.

 

주어진 수는 1 ~ 10000의 수가 주어진다 하였으므로 해당 수를 이분탐색해서 mid값으로 분할을 할 수 있는지 본다. 즉 정리하면

1. 0 ~ 10001 범위에서 mid를 잡는다. 해당 mid는 구간 내 차이의 값을 의미한다.

2. 해당 mid값으로 구간을 나눠보고 전부 나눴을 때 구간의 개수를 반환받는다.

3 -1. 구간의 개수가 주어진 구간의 개수보다 작거나 같다면 => 더 값을 낮출 수 있다는 의미이므로 right = mid - 1이 된다.

3-2. 구간의 개수가 주어진 구간의 개수보다 크다면 => 더 값을 높여줘야 한다는 의미이므로 left = mid + 1이 된다.

 

이렇게 계속 돌다가 더이상 값을 줄일 수 없는 left가 right를 초과하게 되면 반복을 종료하고 그때의 left를 반환한다. 이 값이 M개의 구간을 만들면서 낼 수 있는 최소 차이값이 된다.

 

🐢코드

package 이분탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 구간나누기2_13397 {
    static int N, M;
    static int[] nums;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        binarySearch();
    }

    private static void binarySearch() {
        int divCount;
        int left = 0;
        int right = 10001;
        int mid;

        while (left <= right) {
            mid = (left + right) / 2;

            divCount = divide(0, 0, 10001, 0, mid);
            if (divCount <= M) right = mid - 1;
            if (divCount > M) left = mid + 1;
        }
        System.out.println(left);
    }

    private static int divide(int end, int max, int min, int divCount, int diff) {
        if (end == N) return divCount + 1;
        max = Math.max(max, nums[end]);
        min = Math.min(min, nums[end]);
        int tmpDiff = max - min;
        if (tmpDiff <= diff)
            return divide(end + 1, max, min, divCount, diff);
        else
            return divide(end, 0, 10001, divCount + 1, diff);
    }
}

🐢 마무리