백준 13397[자바] java 구간 나누기 2

 

문제 링크: 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], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다.

두 경우 중에서 최댓값이 최소인 것은 5점인 것이고, 5점보다 최댓값을 작게 만드는 방법은 없다.

배열과 M이 주어졌을 때, 구간의 점수의 최댓값의 최솟값을 구하는 프로그램을 작성하시오.

 

▶입력

 

첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)

둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.

 

▶출력

 

첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.

 

▶해설

 

문제를 풀 아이디어가 떠오르지 않아 해설을 봤습니다. 이분 탐색으로 접근합니다. 

 

배열중에서 가장 큰 수를 찾아줍니다.

left = 0, right = 가장 큰 수 라고 설정합니다. 이제 정답에서 요구하는 구간들의 최댓값을 최솟값으로 만족시키는 답이 left ~ right의 사이의 수입니다. 

 

아래와 같이 이분 탐색을 진행합니다. 

while(left<right){
    int mid = (left+right)/2;
    if(solve(mid)<=m){
        right=mid;
    }else{
        left=mid+1;
    }
}

 

solve는 left ~ right 사이의 수가 들어가게 됩니다.

이제 인덱스 0 부터 i까지 점차 증가시키며, 인덱스 중에 가장 큰 수와 가장 작은 수를 찾습니다. 

이때 max-min>mid 라면 구간을 끊습니다. 그 이유는 구간의 가장 최댓값을 mid라고 설정했기 때문에 다음 현재 인덱스는 넣을 수 없습니다. 그리고 구간이 나뉠 때마다 count를 더해줍니다. 

 

예시를 보겠습니다.

8 3

1 5 4 6 2 1 3 7 

 

left =0, right =7, mid = 3이 됩니다. 

 

solve로 들어가서 

1->5 :1과 5의 차이는 4이므로 구간을 나눠줘야 합니다. 따라서 1은 하나의 구간에 담기고 5부터 다시 탐색합니다. 

5 -> 4-> ->6 ->2: 가장 큰 수인 6과 가장 작은 수인 2의 차이가 4입니다. 따라서 5,4,6까지만 구간을 나누고 2부터 다시 탐색합니다. 

2->1->3->7: 가장 큰수인 7과 가장 작은 수인 1의 차이가 6입니다 따라서 2,1,3까지 담고 7부터 탐색합니다.

 

mid=3 일 때 최종적으로{1},{5,4,6},{2,1,3},{7}로 구간이 나뉘었습니다. 여기서 3개 이하의 구간이 아니므로 만족하지 않습니다. 위의 과정을 코드로 나타내면 아래와 같습니다.

 

private static int solve(int mid){
    int count = 1;
    int min = MAX;
    int max = -MAX;
    for(int i=0; i<n; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
        if(max - min > mid) {
            count++;
            max = -MAX; min = MAX;
            i--;
        }
    }
    return count;
}

 

이제 다시 이분 탐색으로 돌아가 left=mid+1로 들어가게되고 left>=right가 되기 전까지 반복됩니다. 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;


public class Main {


    static int n,m, MAX = 987654321;;
    static int []arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        arr = new int[n];

        int right = Integer.MIN_VALUE;
        String[] s1 = br.readLine().split(" ");
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(s1[i]);
            right = Math.max(arr[i],right);
        }

        int left= 0;

        while(left<right){
            int mid = (left+right)/2;
            if(solve(mid)<=m){
                right=mid;
            }else{
                left=mid+1;
            }
        }

        System.out.println(right);
    }
    private static int solve(int mid){
        int count = 1;
        int min = MAX;
        int max = -MAX;
        for(int i=0; i<n; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
            if(max - min > mid) {
                count++;
                max = -MAX; min = MAX;
                i--;
            }
        }
        return count;
    }
}