[BOJ] 17071 숨바꼭질 5 - P5

TaeGN·2024년 8월 27일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

37/114

문제풀이

t1시간에 동생이 도달할 지점을 t2시간에 도착했다 했을 때, (t1 - t2)가 짝수이면 동생과 만날 수 있다.
도착 시간이 홀수, 짝수일 경우를 나눠서 각각의 최단 시간을 구한다.
동생이 도착할 지점을 하나씩 순회하며 조건을 만족하는 값이 있는지 판단한다.

주의사항

소요시간

40분

package 백준.Platinum.P5.p17071_숨바꼭질5

const val IMPOSSIBLE = Int.MAX_VALUE shr 2
const val EVEN = 0
fun main() {
    val (N, K) = readln().split(" ").map(String::toInt)
    val dp = Array(2) { IntArray(500001) { IMPOSSIBLE } }
    val queue = ArrayDeque<Int>()
    val visited = Array(2) { BooleanArray(500001) }
    fun add(time: Int, value: Int) {
        val type = time % 2
        if (value in 0..500000 && !visited[type][value]) {
            queue.add(value)
            visited[type][value] = true
            dp[type][value] = time
        }
    }

    var t = 0
    add(EVEN, N)
    while (queue.isNotEmpty()) {
        t++
        repeat(queue.size) {
            val n = queue.removeFirst()
            add(t, n + 1)
            add(t, n - 1)
            add(t, n * 2)
        }
    }

    fun result(): Int {
        var time = 0
        while (K + time * (time + 1) / 2 <= 500000) {
            val type = time % 2
            if (dp[type][K + time * (time + 1) / 2] <= time) return time
            time++
        }
        return -1
    }
    println(result())
}