[Algorithm] Parametric Search

 

정의

최소/최대 값을 구하는 최적화 문제를 결정 문제로 변환하여 이분탐색으로 풀이하는 방식

 

$$ O (Log N) $$ 으로 시간 복잡도를 줄일 수 있게한다.

 

When to use?

최소/최대 값이라는 용어가 주어지고, 해당 값의 변화가 단조 증가 혹은 단조 감소 함수 일때 파라메트릭 서치가 사용 가능한지 떠올려 볼 수 있다.

 

대표적인 예시가 다음과 같은 랜선 자르기 문제다.

 

 

🔒 문제

 

 

 

🧠 아이디어

gif 로 그림이 움직입니다.

 

 

🔑 Kotlin Code

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

private fun getLowerBoundLength(cables: LongArray, N: Int) : Long{
    var left: Long = 1
    var right = cables.last()

    while (left < right) {
        val mid = (left + right) / 2
        // Get sum of lan cable count
        val midCnt = cables.sumOf { it / mid }

        // 길이가 최대려면 left 를 return 해야..
        if (midCnt >= N) left = mid + 1
        else right = mid
    }

    // 길이 결정시 초과길이가 나온 경우 더 짧은 길이 결정
    if (cables.sumOf { it / left } < N) return left - 1
    // 딱맞는 길이는 바로 return
    return left
}


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (K, N) = br.readLine().split(" ").map(String::toInt)

    val cables = LongArray(K)

    repeat(K){ cables[it] = br.readLine().toLong() }
    cables.sort()

    print(getLowerBoundLength(cables, N))
}