백준 1654번 랜선자르기 - kotlin

오늘은 이진탐색 문제중 랜선 자르기 라는 문제를 풀어보았다

19%라는 낮은 정답률을 가진 난이도 있어보이는 문제였고, 과감히 도전하였다

​

문제

​

접근방법

MIN값과 가장 긴 랜선의 길이를 MAX값으로 잡고 두 값을 더해 2로 나눈 MID값으로 이진탐색

여기서 중요한 부분은 min,max값을 Long타입으로 선언해주는 것이다

그 이유는 랜선의 길이가 최대 2의 32제곱까지 가능하고, mid를 구하기위해 min과 max의 값을 더해주는 과정에서 Int의 범위를 벗어나기때문에 Long으로 선언해야한다.

​

풀이소스

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (K, N) = readLine().split(" ").map { it.toInt() }
    val arr = Array(K, { 0 })    
    var min: Long = 1 //최소값 
    var max: Long     //최대값
    var mid: Long     //중간값

    //랜선 길이 입력
    for (i in 0 until K) {
        arr[i] = readLine().toInt()
    }
    
    arr.sort() //정렬

    max = arr[K - 1].toLong() //최대값을 어레이의 마지막값으로 세팅

    while (min <= max) {
        //중간값( 랜선을 나눌 기준 길이 )
        mid = (min + max) / 2

        //랜선의 갯수
        var count:Long = 0

        for (i in 0 until K) {
            count += arr[i] / mid  // 랜선길이/기준길이 의 몫 만큼 카운트 증가
        }

        if (count >= N) {  //목표개수보다 같거나 크면
            min = mid + 1  //최소값 재설정
        } else max = mid - 1  //아니면 최대값 재설정
    }
    print(max)
}

위 사진처럼 런타임에러가 자꾸나서 뭐 때문인지... 삽질을 엄청했다..

하지만 결국 답을 찾아냈고 그 이유는 Long 타입을가진 min변수를 0으로 초기화 했기 때문이었다.

Long이 0이 되는걸로 알고있는데 왜 이러는지 잘 모르겠다. 한번 찾아봐야겠다.