백준 22254 공정 컨설턴트 호석 Kotlin (이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/22254

22254번: 공정 컨설턴트 호석

문제

거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 N개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정해져있다. 주문의 번호는 1번부터 N번까지 매겨져 있으며, 다음과 같은 규칙에 맞게 공정이 이뤄진다.

1. 공정 라인이 총 K개가 있다면 1번부터 K번까지의 번호가 존재한다.
2. 공정 라인의 사용 시간은 배정된 맞춤형 선물들의 제작 시간의 총합이다.
3.  i번 선물은 1번 부터 i−1번 선물들이 배정된 이후에 사용 시간이 가장 적은 공정 라인 중 하나에 배정된다.

모든 맞춤형 선물의 제작이 완료될 때까지 최대 X시간이 남아있는 상황인데, 아직 공정 라인의 개수 K가 정해져 있지 않다. 류진국 사장은 이 분야 최고 권위자, 공정 컨설턴트 호석에게 의뢰했다. 공정 컨설턴트 호석은 최소한의 비용을 쓰기 위해서 공정 라인의 개수를 최소화 시키고자 한다. 호석을 도와 필요한 최소 공정 라인 개수를 계산하자.

입력

첫 번째 줄에 맞춤형 선물 주문의 개수 N, 제작 완료까지 남은 시간 X가 공백으로 구분되어 주어진다.

두 번째 줄에는 1번부터 N번 선물이 필요한 공정 시간이 순서대로 주어진다. 단위는 '시간' 이다.

출력

모든 선물을 X시간 이내에 제작하기 위해 필요한 최소 공정 라인 개수를 출력하라.

제한

•  1≤N≤100,000, N은 자연수이다.
•  1≤X≤109, X는 자연수이다.
•  1≤ 각 선물의 공정 시간 ≤X, 모든 시간은 자연수이다.

알고리즘 분류

• 자료 구조
• 이분 탐색
• 우선순위 큐
• 매개 변수 탐색

풀이

우선순위 큐를 이용하는 문제이다.

비슷한 유형의 문제들이 코테에서 종종 보인다.

공정을 2개로 한다고 하면,

우선 2개의 공정(우선순위 큐, 최소힙)에 오더 순서대로 두 개의 선물을 돌리고,

이후 남은 선물들을 두 개의 공정에 우선순위 큐에서 탑에 있는 공정에 추가해 나간다.

만약 공정에서 선물을 제작하는 과정에서 주어진 시간 X를 넘게 된다면, 2개의 공정으로는 시간 내에 모든 선물을 제작할 수 없는 것이다.

 

우리는 시간 내에 모든 선물을 제작할 수 있는 공정의 수를 구해야 하고, 이 공정의 수를 최솟값으로 구해야 한다.

공정의 수는 최소 1개 ~ 최대 n개 내에서 모든 선물을 제작할 수 있는 공정의 수가 나오기 때문에,

1부터 n까지의 공정의 수를 검사하면 된다.

 

이를 선형 탐색으로 구현한다면,

1부터 n까지의 공정의 수를 검사하는 데에 n

우선순위 큐에 1부터 n 개의 선물을 넣는 데에 n

우선순위 큐의 내부 정렬에 logn

즉 O(N^2*logn)의 시간 복잡도로 시간 초과가 날 것이다.

 

따라서 1부터 n까지의 공정의 수를 검사하는 데에 이분 탐색을 이용할 수 있다.

1부터 n까지의 공정의 수를 검사하는 데에 logn

우선순위 큐에 1부터 n 개의 선물을 넣는 데에 n

우선순위 큐의 내주 벙렬에 logn

즉 O(NlogN * logN)의 시간 복잡도로 통과할 수 있다.

 

코드1

import kotlin.math.*
import java.util.*

//1<= n <=100000 선물 주문의 개수
//1<=x<=1000000000 완료까지 남은 시간
//공정 개수를 구해야 함
//공정 개수 하나부터 다 검사
//그냥 검사하면 n^2
//이분 탐색하면 nlogn*logn
//우선순위큐 logn

fun check( mid : Int, input : LongArray, limit : Int):Boolean{
    val pq =PriorityQueue<Long>()
    for(i in 0 .. mid){
        pq.add(input[i])
    }
    for(i in mid+1 until input.size){
        val cur = pq.poll()
        if(cur+input[i]>limit){
            return false
        }
        pq.add(cur+input[i])
    }
    return true
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,x) = br.readLine().split(' ').map{it.toInt()}
    val input = br.readLine().split(' ').map{it.toLong()}.toLongArray()

    var s = 0
    var e = n
    while(s<e){
        val mid = (s+e)/2
        if(check(mid,input,x)) {
            e=mid
        }
        else
            s = mid+1
    }
    write("${e+1}")
    close()
}

코드2

import kotlin.math.*
import java.util.*

//1<= n <=100000 선물 주문의 개수
//1<=x<=1000000000 완료까지 남은 시간
//공정 개수를 구해야 함
//공정 개수 하나부터 다 검사
//그냥 검사하면 n^2
//이분 탐색하면 nlogn*logn
//우선순위큐 logn
var answer=987654321
fun biSearch(start : Int, end : Int, limit : Long, input : LongArray ){

    if(start>=end){
        return
    }
    val mid = (start+end)/2
    val pq = PriorityQueue<Long>()
    var idx=0
    while(idx<=mid && mid<input.size){
        pq.add(input[idx++])
    }
    var skip =false
    while(idx< input.size){
        val cur = pq.poll()
        if(cur+input[idx]>limit){
            skip =true
            break
        }
        pq.add(cur+input[idx++])
    }
    if(!skip) {
        if(pq.isNotEmpty())
            answer = min(answer, mid+1)
        biSearch(start,mid,limit,input)
    }
    else {
        biSearch(mid + 1, end, limit, input)
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,x) = br.readLine().split(' ').map{it.toInt()}
    val input = br.readLine().split(' ').map{it.toLong()}.toLongArray()

    biSearch(0,n,x.toLong(),input)
    write("$answer")
    close()
}