자바 - 백준 13397 / 구간 나누기 2

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

골드4

 

구현 방법

처음에 dfs 이용한 완전탐색 생각했습니다.

하지만 배열의 크기가 5000이고 나눌 수 있는 횟수가 5000이라서 최대 2^5000(구간 당 나눈다/안나눈다.)로 시간초과가 날게 뻔했습니다. => 시간복잡도 : O(2^(배열의 길이))

 

매개변수 탐색

해당 문제는 나눈 구간별 (최댓값 - 최솟값)의 최댓값의 최솟값을 구하는게 목표 입니다.

또한 이 최대값의 최솟값 범위는 0 ~ 10000 사이입니다.(배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 조건 때문) 따라서 목표값을 기준으로 이분탐색을 진행하면서 해당 목표값을 구간을 나누어서 나올 수 있는 값인지를 판단하면 됩니다.

 

구간을 나누어서 목표값이 가능한지 판단하는 방법은 다음과 같습니다.

1. 배열의 처음부터 하나씩 늘려가며 최댓갑과 최솟값을 구합니다.

2. (최댓값 - 최솟값)이 목표값을 초과하는지 판단합니다.

    2-1. 초과하는 경우 구간을 나누어주고 나눈 구간 횟수를 증가시킵니다.

    2-2. 초과하지 않는 경우 1번을 반복합니다.

 

시간복잡도: O(logN * N), 매개변수 탐색 * 목표값 가능 여부 확인

코드

import java.util.*;
import java.io.*;

/**
 * 백준 13397
 * 구간 나누기 2
 * 골드4
 * https://www.acmicpc.net/problem/13397
 */
public class BOJ13397 {

    static int[] array;
    static int N;
    static int M;

    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()); // 나누는 횟수

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

        int left = 0;
        int right = 10000;
        int answer = right;

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

            if(canDivide(mid)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(answer);
    }

    public static boolean canDivide(int v) {
        int count = 1;
        int min = array[0];
        int max = array[0];

        for(int i = 1; i < N; i++) {
            min = Math.min(min, array[i]);
            max = Math.max(max, array[i]);

            if(max - min > v) {
                count++;
                min = array[i];
                max = array[i];
            }
        }

        return count <= M;
    }
}