[백준 13397] - 구간 나누기2(Kotlin)[골드4]

문제

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

13397번: 구간 나누기 2

문제 풀이

문제에서 요구하는 바를 이해하기 정말 어려웠던 문제였다.

구간의 점수의 최댓값의 최솟값이라니,,

 

입력을 살펴보면 배열의 크기가 1부터 5000이고, 구간의 개수가 M개 이하이다.

배열에 대해서  M개 이하의 구간으로 분리하고, 각 구간에서 구간의 점수를 구하고, 구간의 점수중 최댓값이고,

그중에서 최솟값을 구해야 한다.

 

말로만 적어봐도 경우의 수가 굉장히 많은 것을 알 수 있다.

5000에서 구간의 개수를 정하는 것 + 정확한 구간을 정하는 것 + 구간의 점수 구하기 등등만 해도 일반적인 문제가 아닌 최적화 문제라는 것을 알 수 있다.

 

디피와 그리디보단 이분탐색에 가까워 보였고, 탐색의 시작점과 끝점, 결정조건에 대해서 고민해 봤다.

 

나무 자르기, 랜선 자르기 등 구하고자 하는 길이에 대해서 조건을 만족하는지를 결정하는 문제가 대부분의 이분탐색 문제였다.

 

해당 문제도 구하려고 하는 답인 구간의 점수의 최댓값의 최솟값에 대해서 특정 값(mid)이 만족하는지 결정하는 문제이다.

 

하지만 구간을 어떻게 나눠야 하는지 감이 안 잡혀서 답을 보게 되었다.

내가 간과했던 사실은 [7]이라는 구간이 존재한다면 구간의 점수는 0이라는 점이다.

 

해당 정보를 바탕으로 구간을 어떻게 나누는지 살펴보자

 

내가 정한 이분탐색의 결정문제는 mid값보다 큰 구간의 점수를 가지는 구간이 있느냐, 없느냐이다.

 

예제 케이스로 살펴보자면,

1 5 4 6 2 1 3 7의 배열이 있고, 구간의 최대 개수는 3이다.

 

이분탐색은 다음과 같이 진행된다.

1. 초기 left와 right의 값은 0과 배열의 최댓값인 7이다.
   • 여기서 left와 right 값의 의미는 구간이 만들 수 있는 점수의 최솟값과 최댓값을 의미한다.
2. left와 right 합의 절반인 mid를 구하고 mid에 대해서 mid를 최대로 구간을 나눌 수 있는지를 검사한다.
   • 여기서 구간을 나눌 수 있다면 더 작은 mid값에 대해서 검사를 하기 위해 right = mid -1 오른쪽의 범위를 좁힌다.
   • 구간을 나눌 수 없다면 더 큰 mid 값에 대해서 검사를 하기 위해  left = mid +1, 왼쪽의 범위를 넓힌다.
     • 여기서 구간을 나눌 수 없다는 뜻은 mid가 최대값인 구간을 만드는데 필요한 구간의 수가 M개 초과인 경우이다.
3. 경계지점까지 이분탐색을 진행한 후(left와 right의 범위가 역전되었을 때, 그때의 경계포인트에서 반환할 지점을 정해야 한다.

결정문제는 다음과 같이 진행된다.

배열을 탐색하면서 최댓값과 최소값을 계속해서 업데이트하고, 최대값과 최솟값의 차이가 mid 값보다 커진다면 구간의 개수를 추가해주고, 최대값과 최솟값을 다시 갱신한다.

 

이분탐색과 예제를 통해서 과정을 함께 해보면 다음과 같습니다.

 

최종적으로 left와 right가 엇갈리는 지점에서 반환해야 할 값은 left이다.

이렇다 할 방법이 있다기보단 테스트케이스에 대해서 내가 만든 이분탐색을 진행하고 테스트케이스의 답을 통해서 left와 right를 정한다.

 

전체 코드

import kotlin.math.*

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private var m = 0
    private lateinit var graph: IntArray
    fun run() {
        input()
        print(solve())
    }

    private fun input() {
        br.readLine().split(" ").map { it.toInt() }.apply {
            n = this[0]
            m = this[1]
        }
        graph = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }

    private fun solve(): Int {
        var left = 0 // 구간의 점수 최대가 0이 될 수 있음.
        var right = graph.max()

        while (left <= right) {
            val mid = (left + right) / 2
            if (countGroup(mid)) { //mid가 최대인 구간을 만들 수 있니?
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return left
    }

    private fun countGroup(maxSum: Int): Boolean {
        var minGroup = Int.MAX_VALUE
        var maxGroup = Int.MIN_VALUE
        var groupCnt = 1
        graph.forEach { num ->
            minGroup = min(minGroup, num)
            maxGroup = max(maxGroup, num)

            if (maxGroup - minGroup > maxSum) { //최대와 최소의 차이가 maxSum보다 클 경우 구간을 자름.
                groupCnt++
                minGroup = num
                maxGroup = num
            }
        }
        return groupCnt <= m
    }
}

fun main() {
    Solution().run()
}