백준 13397번: 구간 나누기 2 (Kotlin)

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

13397번: 구간 나누기 2

 

안녕하세요, 이륙사입니다.

 

어제 백준에서 구간 나누기2 문제를 풀어봤습니다. 이전에 풀어본 유형이어서 알고리즘은 떠올랐지만 구체적인 풀이법이 떠오르지 않더라구요. 왜 그렇게 풀어야했는지 제대로 이해하지 못하고 넘어갔던 것 같아서 이번 기회에 정리해보려고 합니다.

 

선 정리

1. 구간을 어떻게 나눌까 -> 반대로 접근해서 구간 점수의 최대값을 기준으로 구간을 나눌 수 있는지 확인한다. -> 이분 탐색
2. 점수 최대값의 범위: 0 ~ (배열 최대값 - 최소값)
3. 구간을 나눌 때, 구간마다 최대한 길게 만든다 -> M개 이하가 될 확률을 높일 수 있음
   1. M개 이하로 나누는데 성공 -> 더 점수를 낮춰도 나눌 수 있는지 확인 -> upper = mid - 1
   2. M개 이하로 나누는데 실패 -> 점수를 더 높여서 확인 -> lower = mid + 1  
   3. 왜? 우리의 목표는 점수 최대 값의 최소값을 구하는 것이며, 구간 당 가능한 점수가 클수록 구간의 길이가 길어질 확률이 높아지기 때문이다. 

후 풀이

언뜻 읽어보면 점수의 최댓값의 최솟값, 말이 좀 복잡해 보입니다. 저는 구간을 나누면 점수가 계산되고 그 중 최댓값이 존재할텐데, 그 최댓값을 최소로 만들고 싶다. 즉, '구간을 어떻게 나눠야 가장 작은 (점수 최댓값: maxScore)을 구할 수 있을까'라고 이해했습니다. 

 

어떻게 구간을 나눠야 최소값을 얻을 수 있을까에 대한 문제구나 생각하고, 완전 탐색을 먼저 떠올렸습니다. 하지만 M개 이하로 나누기 때문에 시간 복잡도가 팩토리얼 수준으로 나와서 불가능하다고 판단했습니다.

반대로 접근한다

어떻게 해결할 수 있을까,,, 결론적으로 반대로 접근해서 해결할 수 있는 문제였습니다. 즉, 점수 최댓값을 먼저 설정하고, 그걸 기준으로 M개 이하의 구간을 나눌 수 있는지 확인하는 겁니다. 그 과정에서 이분 탐색을 사용합니다.

1. 점수 최대값의 범위는 배열이 하나일 때의 최소값 0에서 배열 내 최대값과 최소값의 차이 즉, 0 ~ (max(array) - min(array))입니다.
2. 이제 점수 (최대값)을 기준으로 구간을 나눠봅니다. 구간마다 최대한 많은 길이를 차지하도록 만듭니다. 왜냐면,
   1. M개 이하로 구간을 나눠야하기 때문에 구간을 최대한 길게 만들수록 성공 확률이 높아집니다.
   2. 앞의 구간에서 최대한 많은 숫자를 가져갈수록, 뒤에 남은 숫자들의 범위가 작아집니다. 그러면 그만큼 뒤에 구간의 점수도 작아질 확률이 높아집니다.
3. M개 이하로 구간을 만들지 못했다면, 점수를 더 크게 해서 구간을 나눌 수 있는지 다시 확인합니다. 반대로 성공했다면, 점수를 더 작게 해도 구간을 나눌 수 있는지 확인합니다. 이렇게 기준을 잡을 수 있는건, 점수가 클수록 구간이 길어질 확률이 높아지기 때문입니다. 즉, 평균적으로 구간마다 더 많은 숫자를 가질 수 있게 됩니다. 그리고, 우리의 목표는 점수 최대값의 최소값을 구하는 것이니까요!

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 입력
    val (n, divideLimit) = readLine().split(" ").map(String::toInt)
    val array = with(StringTokenizer(readLine())){
        IntArray(n){
            this.nextToken().toInt()
        }
    }
    
    var lower = 0
    var upper = array.maxOrNull()!! - array.minOrNull()!!

    if (n == 1) { // 배열 크기가 하나일 때
        print(0)
        return
    } else if (divideLimit == 1) { // 구간 1개 -> 배열을 나눌 수 없을 때
        print(upper - lower)
        return
    }

    // 점수의 최대값을 기준으로 이분 탐색
    // 점수의 최댓값이 mid가 되도록 구간을 가장 길게 나눠본다
    // 나눌 수 있으면 최소값을 찾기 위해 더 작은 최대값을 찾아본다
    // 나눌 수 없으면 더 큰 최대값을 찾는다
    // 구간의 점수가 커질수록 구간이 길어지고 구간 개수가 작아질 확률이 높아진다 
    while (lower <= upper) {
        val mid = (lower + upper) / 2

        if(isValid(array, mid, divideLimit)) {
            upper = mid - 1
        } else {
            lower = mid + 1
        }
    }

    print(lower)
}

fun isValid(array: IntArray, standard: Int, divideLimit: Int): Boolean {
    var count = 0
    var max = 0
    var min = 10_001

    for (i in array.indices) {
        max = max(max, array[i])
        min = min(min, array[i])

        // 최대값 or 최소값이 더 크/작아져서 더 길게 나눌 수 없을 때
        if (max - min > standard) {
            count++
            max = array[i]
            min = array[i]
        }
    }
    count++ // 마지막 구간

    return count <= divideLimit
}

 

후기

어떻게 생각하면 풀 수 있다는 건 확실히 알게됐지만, 왜 이렇게 접근해야만 하는지는 사실 아직도 와닿지가 않습니다. 이렇게 접근할 수도 있다는 걸 숙지하고, 사고의 폭을 넓혀가야 하는 걸까요? 조금은 답답하기도 한데, 이와 관련해서 댓글로 남겨주신다면 정말 감사하겠습니다.