[BOJ] 1637 날카로운 눈 - P4

TaeGN·2024년 8월 31일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

42/114

문제풀이

1 ~ 임의의 수에서 정수의 숫자를 구하고 그것이 홀수인지 짝수인지 판별한다.
매개 변수 탐색을 통해 위의 1번 과정을 반복하며 정수의 숫자가 홀수인 수를 구한다.

주의사항

정수의 숫자가 홀수인 수가 없을 수도 있다.

소요시간

24분

package 백준.Platinum.P4.p1637_날카로운눈

fun main() {
    val N = readln().toInt()
    val list = mutableListOf<Triple<Int, Int, Int>>()
    repeat(N) { list.add(readln().trim().split(" ").map(String::toInt).let { Triple(it[0], it[1], it[2]) }) }
    fun isPossible(n: Int): Boolean {
        var count = 0L
        for ((A, C, B) in list) {
            if (n >= A) count += (minOf(n, C) - A) / B + 1
        }
        return count % 2 == 1L
    }

    fun search(start: Int = 1, end: Int = 2147483647): Int {
        val mid = ((start.toLong() + end) / 2).toInt()
        if (start == mid) return if (isPossible(start)) start else if (isPossible(end)) end else -1
        return if (isPossible(mid)) search(start, mid)
        else search(mid + 1, end)
    }

    fun count(n: Int): Int {
        var count = 0
        for ((A, C, B) in list) {
            if (n in A..C && (n - A) % B == 0) count++
        }
        return count
    }

    fun result(): String {
        val n = search()
        if (n == -1) return "NOTHING"
        val count = count(n)
        return "$n $count"
    }

    println(result())
}