[백준][Kotlin]2343번 기타 레슨

해당 문제는 이진 탐색을 사용하여 풀 수 있는 문제였습니다.

주어진 자료 중 가장 큰 값이 정답이 될 수 있는 최소값이 되며, 자료의 합이 정답이 될 수 있는 최대 값이 됩니다.

최소값과 최대값의 중간값으로 비교하며, 최대값과 최소값의 증감을 정하여 다시 중간값으로 비교하면서 최적의 해를 찾으면 되는 문제입니다. 

하기는 제가 작성한 해당 문제의 제출 코드와 제출 결과입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.max
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashSet

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt()
    val M = st.nextToken().toInt()
    var arr = IntArray(N){0}
    st = StringTokenizer(br.readLine())
    repeat(N){
        arr[it] = st.nextToken().toInt()
    }
    var start = arr.max()
    var end = arr.sum()

    while(start < end){
        var count = 1
        val mid = (start+end)/2
        var sum = 0
        for(num in arr){
            if(sum + num <= mid){
                sum+=num
            } else {
                sum = num
                count++
            }
        }
        if(count <= M){
            end = mid
        }else{
            start = mid+1
        }
    }
    println(start)

    //bw.flush()
    //bw.close()
}