백준 구간 나누기2 13397

 

구간의 점수는 구간에 속한 수의 최대값 - 최소값을 의미한다.

배열과 M(구간의 개수)이 주어졌을 때 구간의 점수의 최대값의 최소값을 구하는 문제로 즉, N개의수를 M개의 구간으로 나누는 문제이다.

 

t1에 구간의 최대값을, t2에 구간의 최소값을 저장하고

t2 - t1 값이 mid값보다 크면 구간 개수를 하나 카운트하고, 새로운 구간을 시작해주면 된다.

 

import java.util.*;

public class Main {
    static public int m;
    static boolean go(int[] arr, int mid) {
        int t1 = arr[0];
        int t2 = arr[0];
        int ans = 1;
        for(int i = 1; i < arr.length; i++) {
            t1 = Math.min(t1, arr[i]);
            t2 = Math.max(t2, arr[i]);
            if(t2 - t1 > mid){ //새로운 구간 갱신
                ans += 1;
                t1 = arr[i];
                t2 = arr[i];
            }
        }
        return ans <= m;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        m = sc.nextInt();
 
        int lo = 0, hi = 0;
        int []arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            hi = Math.max(hi, arr[i]);
        }

        int ans = hi;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if(go(arr.clone(), mid)) {
                hi = mid - 1;
                ans = mid;
            } else {
                lo = mid + 1;
            }
        }

        System.out.println(ans);
    }
}

 

*구간을 나누는 방식이 너무 어려웠디.