백준 13397 구간 나누기 2 Kotlin (파라메트릭 서치)

문제 출처 : 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보다 작거나 같은 자연수이다.

출력

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

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

풀이

오랜만에 푸는 파라메트릭 서치 문제.

이분 탐색을 활용한 '매개 변수 탐색'이란 이름으로 분류된다.

 

우선 문제를 완전 탐색으로 접근해 보자.

M이 최대 5000이다.

M이 5000이라면 구간을 1개, 2개, 3개, ~~~ , 5000개로 나누어봐야 하는데,

5000개의 수를 2개의 구간으로 나누는 경우의 수는 5000C1,

3개의 구간으로 나누는 경우의 수는 5000C2

~~~

5000C5000까지로 구간을 나누는 경우의 수만 해도 완전 탐색으로 구할 수 없다.

즉, 다른 방식으로 문제를 접근해야 한다.

 

우리가 구해야 하는 값은 '구간의 점수의 최댓값을 최소화한 값'이다.

만약 배열 내에 수가 10000이 있다고 하면 10000-10000 = 0 혹은 10000-x로 우리가 구하는 값은 러프하게 0부터 10000까지의 범위 내에 있다.

해당 범위 내에서 '구간의 점수의 최댓값을 최소화한 값'을 mid라 정의하자.

그럼 left = 0, right = 10000으로 두고 mid값을 이분 탐색으로 찾을 수 있다.

이분 탐색은 해당 리스트가 정렬되어 있어야만 가능하지 않나?

이 문제에서 우리가 이분 탐색할 리스트는 input으로 주어진 리스트가 아닌 0부터 10000이라는 리스트이다.

 

이제 mid값을 어떻게 구할 수 있을지 생각해야 한다.

만약 해당 mid값이 답이 될 수 있다면 가능한 한 mid를 작게 만드는 것이 정답이므로 mid를 줄여서 시도해 보고,

mid값이 답이 될 수 없다면 mid를 키워서 시도해 본다.

이는 다음과 같이 구현할 수 있다.

    var left = 0
    var right = input.maxOrNull()!!
    var answer = Int.MAX_VALUE
    //solve
    while(left <= right){
        val mid = (left + right)/2
        if(canMid(mid,m,input)){
            answer = mid
            right = mid - 1
        }else{
            left = mid + 1
        }
    }

이제 mid가 답이 될 수 있는지, canMid함수를 구현해야 한다.

첫 번째 예제에서 mid를 4라고 설정했다고 해보자.

8 3

1 5 4 6 2 1 3 7

1,5,4 까진 최댓값과 최솟값의 차이가 mid 이하이다.

1,5,4,6까지 오면 최댓값과 최솟값의 차이가 5이므로 mid값 보다 높다.

이때 구간을 나눌 수 있다. 앞에 1,5,4를 하나의 구간으로 만들고 6부터 다시 시작하자.

6,2,1까지 오면 또 차이가 5로 mid값 보다 높다.

6,2를 하나의 구간으로 만들고 1부터 다시 시작한다.

1,3,7까지 오면 또 차이가 6으로 mid값 보다 높다.

1,3을 하나의 구간으로 만들고 7부터 다시 시작한다.

더 이상 수가 없으니 마지막 구간은 7만 있으므로 7-7 = 0으로 mid값 보다 낮다.

이렇게 했을 대 우리는 몇 개의 구간을 나눴는가

1,5,4 / 6,2 / 1,3 / 7

4개의 구간이다.

하지만 우리에게 허락된 구간은 m = 3으로 이는 mid가 될 수 없음을 의미한다.

이 과정을 canMid라는 함수에 구현하면 끝.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()){

    //input
    val (n,m) = getIntList()
    val input = getIntList()
    var left = 0
    var right = input.maxOrNull()!!
    var answer = Int.MAX_VALUE
    //solve
    while(left <= right){
        val mid = (left + right)/2
        if(canMid(mid,m,input)){
            answer = mid
            right = mid - 1
        }else{
            left = mid + 1
        }
    }
    //output
    write("$answer")

    close()
}

fun canMid(mid: Int,m: Int, input: List<Int>): Boolean {
    var min = Int.MAX_VALUE
    var max = 0
    var mCnt = 1
    for(num in input){
        min = min.coerceAtMost(num)
        max = max.coerceAtLeast(num)
        if(max - min > mid){
            max = num
            min = num
            mCnt++
        }
        if(mCnt > m) return false
    }
    return true
}