[백준] 13397번 : 구간 나누기2 -자바(JAVA)

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

13397번: 구간 나누기 2

 

문제 해석

N개의 수로 이루어진 1차원 배열이 있다.

배열을 M개 이하의 구간으로 나누어 구간의 점수를 최댓값을 최소로 하려고 합니다.

1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.

2. 배열의 각 수는 모두 하나의 구간에 포함되어야 한다.

 

이때 구간의 점수는 구간에 속한 수의 최댓값과 최솟값의 차이입니다.

 

예를 들어 배열이 1 5 4 6 2 1 3 7이며 M = 3입니다.

이때 [1,5] [4,6,2] [1,3,7]로 구간을 나누면 각 구간의 점수는 4 4 6입니다.

이때 최댓값은 6입니다.

 

하지만 구간을 [1 5 4] [4 6 2] [3 7]으로 나누었다면 각 구간의 점수는 4 5 4점입니다.

이때 최댓값은 5점입니다.

 

두 경우 중에서 최댓값이 최소인 것은 5점이며 5점보다 최댓값을 작게 만드는 방법이 없기 때문에 5가 정답입니다.

 

문제 풀이 전 설계

만약 모든 구간을 M개이하 1개 이상으로 나누어서 최댓값 최솟값을 검사하려면 엄청나게 많은 경우를 계산해야 합니다.

따라서 구간의 최댓값을 특정 범위로 가정하고 이를 이분 탐색으로 찾아나가는 과정을 선택합니다.

 

예를 들어 1 5 4 6 2 1 3 7에서 발생할 수 있는 최솟값은 0이고 최댓값은 6입니다.

자기 자신 - 자기자신 = 0

최댓값 7 - 1 = 6

 

따라서 구간의 최댓값이 최소인 값은 0~6 사이로 나올 수 있습니다.

0~6 사이의 값을 통해 이분 탐색으로 값을 구해나갑니다.

 

코드

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

public class Main_구간나누기2_13397 {
    static final int INF = Integer.MAX_VALUE;
    static int n,m;
    static int[] arr;

    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());
        arr = new int[n];

        int left = 0;
        int right = -1;
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, arr[i]);
        }

        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (solve(mid)) {
                //만약 구간이 m개 이하라면 더 작은 값을 탐색
                right = mid - 1;
            } else {
                //만약 구간이 m개 이상이라면 더 큰값을 탐색
                left = mid + 1;
            }
        }

        //+1을 한 이유는 right = mid -1 을 진행하고나서 left <= right를 만족하지 않아서 끝나버리는 경우
        System.out.println(right+1);

    }

    static boolean solve(int mid){
        int cnt = 1;
        int min = INF;
        int max = -INF;

        //구간을 탐색시작
        //만약 max - min > mid인 지점이 온다면 그 전까지는 하나의 구간으로 보고 다음구간을 탐색
        for(int i=0; i<n; i++){
            min = Math.min(min,arr[i]);
            max = Math.max(max,arr[i]);
            if(max - min > mid){
                cnt ++;
                max = -INF;
                min = INF;
                i--;
            }
        }

        //구간이 m개 이하로 나와야한다.
        return cnt <= m;
    }

}