[BOJ] 10670 Moovie Mooving - P3

문제풀이

1. dp[방문 여부] = 최대 시간으로 두고 dp테이블을 채워나간다.
2. dp의 값이 L이상인 것들 중에서 방문 횟수가 최소인 것을 구한다.

---

주의사항

---

소요시간

35분

---

package 백준.Platinum.P3.p10670_MoovieMooving

const val IMPOSSIBLE = Int.MIN_VALUE shr 2
fun main() {
    val (N, L) = readln().trim().split(" ").map(String::toInt)
    val dp = Array(1 shl N) { IMPOSSIBLE }.apply { this[0] = 0 }
    val movieArr = Array(N) { mutableListOf<Int>() }.apply { this[0].add(0) }
    val dArr = IntArray(N)
    for (i in 0 until N) {
        for ((j, num) in readln().trim().split(" ").map(String::toInt).withIndex()) {
            if (j == 0) dArr[i] = num
            else if (j >= 2) movieArr[i].add(num)
        }
    }
    for (flag in dp.indices) {
        for (i in 0 until N) {
            if ((flag and (1 shl i)) == 0) continue
            val pFlag = flag xor (1 shl i)
            val idx = movieArr[i].binarySearch(dp[pFlag] + 1).let { if (it >= 0) it else -it - 1 } - 1
            if (idx >= 0) dp[flag] = minOf(L, maxOf(dp[flag], movieArr[i][idx] + dArr[i]))
        }
    }
    var result = N + 1
    for (flag in dp.indices) {
        if (dp[flag] >= L) result = minOf(result, flag.countOneBits())
    }
    println(if (result == N + 1) -1 else result)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P3/p10670_MoovieMooving/p10670_MoovieMooving.kt

---

문제링크

https://www.acmicpc.net/problem/10670