백준 1005번: ACM Craft

문제: https://www.acmicpc.net/problem/1005

문제 풀이

DP + 위상 정렬

$prev[i] = i$번 건물을 짓기 위해 지어야 하는 건물 수

$next[i] = i$번 건물을 지은 후에 지을 수 있는 건물 리스트

$dp[i] = i$번 건물을 건설 완료하는데 걸리는 최소 시간

$D[i] = i$번 건물을 건설에 걸리는 시간

$dp[i] = max(dp[i], dp[j] + D[i])$ $($단 $j$는 $i$번 건물을 짓기 전에 지어야 하는 건물의 번호$)$

$prev$가 0인 건물부터 점화식에 맞게 $dp$값을 채우면 $dp[W]$가 정답

풀이 설명

건물을 짓기 위해서는 건물을 짓는 순서에 따라 먼저 지어야 하는 건물이 지어져야 한다. 그러므로 건물을 건설 완료하는데 걸리는 최소 시간은 먼저 지어야 하는 건물의 건설 완료 최소 시간에 건물 건설에 걸리는 시간을 더한 값이 될 것이다.

따라서 $dp[i]$를 $i$번 건물을 건설 완료하는데 걸리는 최소 시간이라고 정의하면 다음과 같이 점화식이 나온다.

$dp[i] = max(dp[i], dp[j] + D[i])$ $($단 $j$는 $i$번 건물을 짓기 전에 지어야 하는 건물의 번호$)$

그 뒤에 값을 건물을 지어야 하는 순서대로 확인하기 위해 $prev$값을 확인해 지을 수 있는 건물만 큐에 집어넣는다. 큐에 들어간 건물들은 현재 지을 수 있는 건물이므로 $dp$에 건물을 건설하는데 걸리는 시간$D$의 값을 더해준다. 현재 확인하는 건물의 번호를 $x$, $x$를 지은 후에 지을 수 있는 건물을 $y$라고 하면 $y$를 짓기 위해 지어야 하는 모든 건물의 건설 완료 최소 시간을 구하기 위해 $dp[x]$와 $dp[y]$값을 비교해 현재 $dp[x]$의 값이 저장된 $dp[y]$의 값보다 크다면 $y$가 $x$가 건설 완료된 후에 건설해야 된다는 점을 반영하기 위해 $dp[y]$에 $dp[x]$값을 대입한다.

이런 과정을 모든 건물에 대해 처리하면 건물을 건설 완료하는데 걸리는 최소 시간이 $dp$ 테이블에 저장되어 있으므로 $dp[W]$를 출력하면 정답이다.

소스 코드

import java.util.StringTokenizer

fun main(){
    val br = System.`in`.bufferedReader()
    val T = br.readLine().toInt()
    for(i in 1..T){
        var st = StringTokenizer(br.readLine())
        val N = st.nextToken().toInt()
        val K = st.nextToken().toInt()
        val D = IntArray(N + 1){0}
        st = StringTokenizer(br.readLine())
        for(i in 1..N){
            D[i] = st.nextToken().toInt()
        }
        val prev = IntArray(N + 1){0}
        val next = Array(N + 1){ArrayList<Int>()}
        val dp = IntArray(N + 1){0}
        for(i in 1..K){
            st = StringTokenizer(br.readLine())
            val X = st.nextToken().toInt()
            val Y = st.nextToken().toInt()
            prev[Y]++
            next[X].add(Y)
        }
        val queue = ArrayDeque<Int>()
        for(i in 1..N){
            if(prev[i] == 0) queue.add(i)
        }
        while(queue.isNotEmpty()){
            val x = queue.removeFirst()
            dp[x] += D[x]
            for(y in next[x]){
                if(dp[y] < dp[x]) dp[y] = dp[x]
                prev[y]--
                if(prev[y] == 0) queue.add(y)
            }
        }
        println(dp[br.readLine().toInt()])
    }
}