1005. ACM Craft

 

아이디어

어떤 건물을 짓기 위해서는 선행되어야 하는 건물들을 다 짓고 난 후에나 이를 지을 수 있다.

그래서 건물 W 를 건설 완료하는데 드는 최소 시간을 dp[W] 로 정의한다면

 

dp[W] = max(dp[선행 건물1], dp[선행 건물2], ...) + Dw

 

 

이 때 선행 건물의 번호가 W 보다 작다는 보장이 없으므로 재귀함수를 통해서 구현하되 한 번 구한 값은 dp 배열에서 가져오는 방식을 사용하면 된다

 

* 문제에서 Dw 의 범위가 0 부터 시작이기 때문에 건설 완료 시간이 0 인 케이스도 존재가 가능하다. 따라서 dp 배열에 대한 초기화는 -1로 해준다

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int[] times;
    static List<Integer>[] graph;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder result = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken()); // 건물의 개수
            int K = Integer.parseInt(st.nextToken()); // 건설 규칙의 개수

            times = new int[N + 1];
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                times[j] = Integer.parseInt(st.nextToken());
            }

            graph = new List[N + 1];
            for (int j = 1; j <= N; j++) {
                graph[j] = new ArrayList<>();
            }

            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());

                int before = Integer.parseInt(st.nextToken());
                int after = Integer.parseInt(st.nextToken());

                graph[after].add(before);
            }

            int W = Integer.parseInt(br.readLine());
            dp = new int[N + 1];
            Arrays.fill(dp, -1);
            result.append(dp(W)).append("\n");
        }

        System.out.println(result);
    }

    public static int dp(int job) {
        if (graph[job].size() == 0) {
            dp[job] = times[job];
        }

        if (dp[job] != -1) return dp[job];

        for (int before : graph[job]) {
            dp[job] = Math.max(dp[job], dp(before) + times[job]);
        }

        return dp[job];
    }
}