bj13397(구간 나누기2)-매개변수탐색

https://www.acmicpc.net/status?user_id=wjdwlgh2000&problem_id=13397&from_mine=1

항상 느끼는 거지만, 분할 정복, 매개변수 탐색 같이 인덱스를 다루는 놈들이 가장 어렵다.

 

매개변수 탐색은 조금더? 라는 생각으로 start나 end 둘중 하나를 mid+1을 넣어가면서 탐색해야한다.

마지막에는 그냥 mid였던 놈을 반환한다.

start = mid+1이었다면 end를 반환해주면 된다.

문제 이해는 쉬웠지만, 항상 구현에서 막힌다.

 

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

public class Main {
    static int N, M;
    static int[] arr;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        int init = initialize();
        System.out.println(findMin(0, init));
    }

    private static int findMin(int start, int end) {
        while(start < end){
            int mid = (start + end) / 2;
            if(divide(mid) > M){
                start = mid+1;
                continue;
            }
            end = mid;
        }
        return end;
    }

    private static int divide(int value) {
        int max = 0, min = Integer.MAX_VALUE;
        int cnt = 1;
        for(int i = 0; i < N; i++){
            max = Math.max(arr[i], max);
            min = Math.min(arr[i], min);
            if(max - min > value){
                cnt++;
                max = 0;
                min = Integer.MAX_VALUE;
                i--;
            }
        }
        return cnt;
    }
    private static int initialize() throws IOException {
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int max = 0;
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
            max = Math.max(max, arr[i]);
        }
        return max;
    }
}