문제풀이
- (N - K)번의 물의 이동을 하면 된다.
- N이 최대 20이므로 비트 마스킹을 이용하여 이동 여부를 체크한다.
- dp[2^N]의 dp테이블을 채운다.
주의사항
소요시간
15분
package 백준.Platinum.P5.p13941_Kronican
const val IMPOSSIBLE = Int.MAX_VALUE shr 2
fun main() {
fun Int.contains(idx: Int) = (this and (1 shl idx)) != 0
fun Int.add(idx: Int) = this or (1 shl idx)
val (N, K) = readln().split(" ").map(String::toInt)
val matrix = Array(N) { readln().split(" ").map(String::toInt) }
fun result(): Int {
val dp = IntArray(1 shl N) { IMPOSSIBLE }.apply { this[0] = 0 }
for (count in 0 until (N - K)) {
for (flag in dp.indices) {
if (flag.countOneBits() != count || dp[flag] == IMPOSSIBLE) continue
for (from in 0 until N) {
if (flag.contains(from)) continue
var minWeight = IMPOSSIBLE
for (to in 0 until N) {
if (from == to || flag.contains(to)) continue
minWeight = minOf(minWeight, matrix[from][to])
}
dp[flag.add(from)] = minOf(dp[flag.add(from)], dp[flag] + minWeight)
}
}
}
var result = IMPOSSIBLE
for (flag in dp.indices) {
if (flag.countOneBits() == (N - K)) result = minOf(result, dp[flag])
}
return result
}
println(result())
}