[6개월 안에 백준 플래티넘 달성하기] 21. ACM Craft 1005

ACM Craft

1005번: ACM Craft

 

문제

 

풀이

사실문제를 이해하는데 더 많은 시간을 할애한 문제입니다.

처음에 문제를 잘못 이해하였는데 이 잘못 이해한 방식으로도 문제에 나와있는 테스트케이스가 모두 통과가 되었습니다. 

그러다 보니 반례를 찾게 되었고 반례를 통해 문제를 제대로 이해할 수 있었습니다.

 

1
5 5
10 20 30 40 50
1 2
1 3
2 4
3 4
5 4
4

답이 90이 나옴

 

(위 예시를 보시고 이해가 되신다면 다시 풀어보시는 것을 추천드립니다.)

---

제가 잘못 이해한 부분은

건물을 짓는 도중에 다른 건물을 지을 수 없다고 생각한 것입니다.

예시

건물을 짓는 도중에 다른 건물을 지을 수 없기 때문에 위의 예시에서 답이 80이 나오는 것을 기대했습니다.

1) 5번 건물 짓고 +10
2) 2번과 4번 건물을 동시에 짓고 + 50
3) 3번 건물 짓고 +10
4) 1번 건물 지음 +10

 

 

하지만 건물을 짓는 도중에 다른 건물을 지을 수 있기 때문에 답은 60이 나옵니다.

1) 2번 건물과 5번 건물을 지음
2) 10초 뒤 5번 건물이 완성되면 4번 건물을 지음 (2번 건물 남은 시간 40초)
3) 20초 뒤 4번 건물이 완성되면 3번 건물을 지음 (2번 건물 남은 시간 20초)
4) 10초 뒤 3번 건물이 완성됨
5) 10초 뒤 2번 건물이 완성됨
6) 마지막 1번 건물 지음 +10초

 

총 10+20+10+10+10로 60초가 나옵니다. 실질적으로 2번 건물을 지을 동안 5,4,3번 건물을 모두 지을 수 있습니다.

 

 

이제 구현 방법입니다.

위상 정렬 방식에 각 시간을 추가적으로 더해주기 때문에 dp를 사용하면 됩니다.

1. 각 도시별 선수 도시의 개수를 배열에 담아줍니다.
2. 목표 도시에 도달할때까지 선수 도시가 0인 도시부터 주변 도시를 탐색하면서 선수 도시를 -1 해주고 시간을 비교해 준 다음 더해주면 됩니다.

 

코드를 보시면 더 이해하기 편하실 겁니다.

import java.io.StreamTokenizer
import java.util.LinkedList

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    var t = input()
    val sb = StringBuilder()

    while(t-- > 0) {
        val N = input() // 건물 개수
        val K = input() // 규칙 개수

        val arr = IntArray(N+1)  // 건물 생성 시간
        repeat(N) {arr[it+1] = input()}

        val map = Array(N+1) {IntArray(N+1)}
        val degree = IntArray(N+1) // 선수 도시 개수
        val dp = IntArray(N+1)     // 현재 건물 생성까지 걸린 시간

        repeat(K) {
            val a = input()
            val b = input()
            map[a][b] = 1
            degree[b]++
        }

        val subject = input()

        // 선수도시가 0인 도시를 큐에 추가 + dp 초기화
        val queue = LinkedList<Int>()
        for (i in 1..N) {
            if (degree[i] == 0) {
                queue.add(i)
                dp[i] = arr[i]
            }
        }

        fun bfs() {
            while (queue.isNotEmpty()) {
                val cur = queue.poll()

                // 목표 도시 도달할 경우 탈출
                if (cur == subject) {
                    return
                }

                for (i in 1..N) {
                    // 선수 도시인 경우
                    if (map[cur][i] == 1) {

                        // i번 도시의 선수 도시들의 dp값 중 최댓값 = 선수 도시 모두 완성되야지 i번 건물을 지을 수 있기 때문
                        // 선수 도시가 2개 이상인 경우 dp[i]에 이미 값이 있을 수 있다.
                        dp[i] = Math.max(dp[i], dp[cur] + arr[i])

                        // 선수도시가 0이 되는 경우 큐에 추가
                        degree[i]--
                        if (degree[i] == 0) {
                            queue.add(i)
                        }
                    }
                }
            }
        }
        bfs()

        sb.appendLine(dp[subject])
    }
    print(sb)
}

 

 

추가적으로 재귀를 이용한 풀이도 있습니다. 

목표 건물에서 재귀적으로 선수 건물로 넘어가서 시간을 비교해주는 방식입니다.

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    var t = input()
    val sb = StringBuilder()

    while(t-- > 0) {
        val N = input() // 건물 개수
        val K = input() // 규칙 개수

        val arr = IntArray(N+1)  // 건물 생성 시간
        repeat(N) {arr[it+1] = input()}

        val map = Array(N+1) {IntArray(N+1)}
        val dp = IntArray(N+1) {-1}     // 현재 건물 생성까지 걸린 시간

        repeat(K) {
            val a = input()
            val b = input()
            map[b][a] = 1
        }

        val subject = input()


        fun dfs(v: Int): Int {
            // 이미 값이 결정된 경우 = 중복방지
            if (dp[v] >= 0) return dp[v]

            var prev = 0

            // 선수 건물 중 최대 시간이 걸린 값을 찾는 과정
            for (u in 1..N) {
                if (map[v][u] == 1) {
                    prev = maxOf(prev, dfs(u))
                }
            }

            dp[v] = prev + arr[v]

            return dp[v]
        }



        sb.appendLine(dfs(subject))
    }
    print(sb)
}