개발해요

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

풀이

길이가 제각각인 k개의 랜선을 일정한 크기 단위로 잘라서 n개 이상을 만들어 내려고 할 때, 그 크기 단위의 최대 값을 구하는 문제였다.

주어진 k개의 랜선으로 n개를 만들지 못하는 경우는 없다고 했으니까, 최소 1cm씩 잘라내면 항상 n개 이상을 구할 수 있다. 반대로 k = n = 1 이라면, 주어진 랜선 중 가장 긴 길이 만큼 자를 수 있다.

랜선의 길이가 21억cm을 넘기 때문에 1cm부터 차례대로 잘라보면 시간 초과가 날 것이다. 특정 크기로 잘라서 나오는 개수와 n을 비교해서 더 길게 잘라볼지, 짧게 잘라야 하는지 결정할 수 있으므로 이진 탐색을 사용할 수 있다.

시간 복잡도:  O(log(2^31)) = 약 31

구현 방법

1. 랜선을 입력 받는다.
2. 최소 길이(m) = 1, 최대 길이(M) = 가장 긴 랜선(or 2^31 - 1)으로 시작해서, 이진 탐색으로 랜선을 잘라보며 정답을 구한다.
   1. 각 케이블들을 길이 (m + M) / 2로 자른 개수의 합(count)을 구한다
   2. if (count >= n) -> 더 길게 잘라도 n개가 넘는지 확인해본다 -> m = (m + M) / 2 + 1
   3. else -> 너무 길게 잘라서 모자르다 -> M = (m + M) / 2 - 1
   4. 위 과정을 m <= M일 때까지 반복한다.
3. 이진탐색이 끝났을 때, M 값이 답이 된다.

코드 1 (구현 방법대로 m <= M일 때까지 탐색하는 방식)

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val k = input[0].toInt()
    val n = input[1].toInt()
    val cables = LongArray(k + 1) // 랜선

    repeat(k) {
        cables[it] = readLine().toLong()
    }

    print(binarySearch(cables, n))
}

fun cutCables(cables: LongArray, divisor: Long): Int {
    var count = 0L

    cables.forEach { cable ->
        count += cable / divisor
    }

    return count.toInt()
}

fun binarySearch(cables: LongArray, minimumCount: Int): Long {
    var answer = 0L
    var lower = 1L
    var upper = Integer.MAX_VALUE.toLong()

    while (lower <= upper) {
        val mid = (lower + upper) / 2  // 이 과정에서 Long 값이 나올 수 있다
        val numberOfCut = cutCables(cables, mid)

        if (numberOfCut < minimumCount) {
            upper = mid - 1
        } else {
            lower = mid + 1
            answer = mid
        }
    }

    return answer
}

코드 2 (m < M일 때까지 탐색하는 방식)

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val k = input[0].toInt()
    val n = input[1].toInt()
    val cables = IntArray(k + 1) // 랜선

    repeat(k) {
        cables[it] = readLine().toInt()
    }

    print(binarySearch(cables, n))
}

fun cutCables(cables: IntArray, divisor: Long): Long {
    var count = 0L

    cables.forEach { cable ->
        count += cable / divisor
    }

    return count
}

fun binarySearch(cables: IntArray, minimumCount: Int): Long {
    var answer = 0L
    var lower = 0L
    var upper = Integer.MAX_VALUE.toLong()
    upper += 1 // while(lower < upper) 방식에서는 최초의 upper가 답인 경우를 구할 수 없어서 1을 더해준다
    
    while (lower < upper) {
        val mid = (lower + upper) / 2
        val numberOfCut = cutCables(cables, mid)

        if (numberOfCut < minimumCount) {
            upper = mid
        } else {
            lower = mid + 1
            answer = mid
        }
    }

    return answer
}

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

풀이

문제가 실버라서 얕봤다가 크게 다쳤다. 조건 자체를 이해하기 어려웠는데, 가장 인접한 두 공유기 사이의 거리를 최대로 하라는 말이 와닿지 않았다. 가장 인접한, 최대 거리??

그래서 마이구미님 블로그(https://mygumi.tistory.com/301)를 참고해서 이해할 수 있었다.

위 말을 맥락적으로 해석하면, 최대한 공평하면서도 간격이 크게 공유기를 설치하라는 것이다. 특정 두 집의 사이의 설치 간격이 너무 커지면, 그만큼 나머지 설치된 집들 사이의 간격은 짧아져서 가장 인접한 설치 거리가 짧아지기 때문이다.

즉, 거리가 가장 가까운 두 공유기 사이의 거리를 k라고 하면, 나머지 인접한 공유기들 사이의 모두 k보다 크거나 같아야 한다.

ex) k = 3,  2 <-> 5 <-> 12 <-> 15 <-> 19  - (공유기가 설치된 위치)

                         3        7           3           4          - (사이 거리) --> 모두 3보다 크거나 같다

이 문제는 이분 탐색의 응용인 파라메트릭 서치를 통해서 해결하는 문제로 알려져 있는데, 방법은 다음과 같다.

1. 가장 인접한 공유기 사이의 거리를 대상으로 이분탐색을 진행한한다.

2. 그 거리보다 크거나 같도록하는 기준을 만족시키면서 왼쪽 집부터 공유기를 설치하면서 갯수를 센다. 

3. 문제에서 주어진 공유기의 개수와 설치한 공유기의 개수를 비교해서, 같거나 더 많이 설치했다면 간격을 늘리고, 더 적게 설치했다면 간격을 줄인다.

4. left(lower) <= right(upper)일 때까지 1~3번을 반복하여 가장 인접한 설치 거리의 상한선을 찾는다.   

여기서 이해가 안갔던 건 왜 왼쪽 집부터 항상 공유기를 설치하느냐는 것이었다. 정확하게 증명하려면 약간의 수학이 필요한듯 한데, 자세한 건 https://www.acmicpc.net/board/view/50802를 참고해보자.

코드

fun main(){
    var n = 0
    var c = 0
    val listOfHouse = mutableListOf<Int>()

    readLine()!!.trim().split(" ").map{ it.toInt() }.let{
        n = it[0]
        c = it[1]
    }

    repeat(n){
        listOfHouse.add(readLine()!!.toInt())
    }
    listOfHouse.sort()	// 정렬: 이분탐색의 전제 조건

    var lower = 1	// 최소 간격
    var upper = listOfHouse.last() - listOfHouse[0]	// 최대 간격: 양 끝 집 사이의 거리
    var answer = upper

    while(lower <= upper){
        val mid = (lower + upper) / 2
        var count = 1			// 공유기 설치한 횟수
        var prevHouseIdx = 0	// 직전에 설치된 집

        // mid보다 인접 간격이 길거나 같도록 설치한다
        for(i in 1 until n){
            if (listOfHouse[i] - listOfHouse[prevHouseIdx] >= mid){
                count++
                prevHouseIdx = i
            }
        }
        
        // c == count -> 간격을 더 늘려도 모두 설치할 수 있는지 확인해본다
        // c < count -> 더 많이 설치됐다 -> 설치 간격을 늘려본다
        if (c <= count){
            lower = mid + 1
            answer = mid
        }else{			// 더 많은 공유기를 설치해야 한다 -> 간격을 줄인다
            upper = mid - 1
        }
    }

    println(answer)
}