백준 나무자르기 2805번 with Kotlin #이진탐색 #이분탐색

겨우 풀었다.. 맞는거같은데 5% 시작하자 마자 오류가나서 김샜다..

// https://hsin.hr/coci/archive/2011_2012/ 대회 사이트에서 테스트케이스 다 돌려보고 문제점을 찾아냈다.

이문제에서 '적어도' 라는 말에 주목을 해야했다.

이분탐색의 반복문을 모두 돌아도 정답을 찾지 못한경우 가장 답에 가까운 해를 찾아내야한다.

그래서 코드 마지막에 Want보다 sum이 작다면 mid를 하나 줄여서 sum을 늘려줘야한다.

그렇지 않은경우에는 그냥 반복문을 통해 구한 mid를 출력하면 된다.

 

fun main(){
    val (num, want) =  readLine()!!.split(" ").map{it.toLong()}
    val list = readLine()!!.split(" ").map{it.toLong()}
    //for(i in 0 until num)
    var start = 0L
    var end = (list.maxByOrNull { it })!!.toLong()
    var mid = (start+ end)/2
    var ans = 0L
    var sum = 0L
    var cheak = false
    while(start<=end){
        mid = (start+ end)/2
        sum=0
        for(i in 0 until num){
            //println(list[i.toInt()]-mid)
            if(list[i.toInt()]-mid<0)
                continue
            else
                sum += list[i.toInt()]-mid
        }
        //println("sum: $sum start: $start end: $end mid: $mid")
        if(sum==want) {
            cheak=true
            break
        }
        else if(sum>want){
            start=mid+1
        }
        else{
            end=mid-1
        }
    }
 
    var sum1=0L
    var sum2=0L
    var mid2 = 0L
    for(i in 0 until num){
        if(list[i.toInt()]-mid<0)
            continue
        else
            sum1 += list[i.toInt()]-mid
    }
    mid2 = mid - 1
 
    if(sum1<want)
        println(mid2)
    else
        println(mid)
    //println("sum1 $sum1 sum2 $sum2")
 
 
}