Baekjoon(Kotlin) - 1300. K번째 수

URL : https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

[ RESULT ]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.min

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val N = br.readLine().toInt()
    val k = br.readLine().toInt()

    var start = 1
    var end = k

    while(start < end) {
        var cnt = 0
        val mid = (start + end) / 2

        for (i in 1..N) {
            cnt += (min((mid / i), N))
        }

        if (cnt < k) { start = mid + 1 }
        else end = mid

    }
    bw.write(start.toString())


    br.close()
    bw.flush()
    bw.close()
}

 

처음에 풀이할 땐, 브루트 포스로 문제를 풀이했다가 시간 초과가 발생했다.

따로 배열을 생성할려 해도, 메모리 초과가 나올거 같아서 포기했다.

 

문제를 해결하지 못하고 풀이를 찾던 중, 

Start Value = 1

End Value = k

Mid Value = (Start + End) / 2

로 설정한 뒤,

 

1 ~ N까지의 반복을 하며 K보다 작거나 같은 값을 count하고 

이 값이 k보다 작은지 큰지에 따라 start와 end 값을 변경해주어서

결론적으로 Start < End 의 조건을 일치하는 경우의 값을 찾으면 되는 문제였다.