[JAVA]백준 2056번: 작업

www.acmicpc.net/problem/2056

2056번: 작업

 

1. 문제 설명

 

수행해야 할 작업 N개와 각각의 작업마다 걸리는 시간, 어떤 작업 X를 수행하기 전에 반드시 먼저 완료되어야 할 작업들이 주어졌을 때 모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 문제.

 

2. 풀이

 

kwoncorin.tistory.com/75

[JAVA]백준 14567번: 선수과목 (Prerequisite)

백준 14567번 선수과목 문제와 유사한 문제이다.

 

선수과목과 마찬가지로 위상 정렬과 다이나믹 프로그래밍으로 풀 수 있다.

 

위상 정렬과 다이나믹 프로그래밍 모두 점화식

 

DP [X]= 작업 X를 수행하기까지 걸리는 시간 = Max(DP [X],DP[Y]+time [X]) (Y는 X의 선행 작업, time[X]= X 작업에 걸리는 시간 )

 

을 이용해 풀 수 있다.

 

 

3. 코드

 

1) 위상정렬

import java.io.*;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int process_num = Integer.parseInt(br.readLine());


		// X 작업만 실행 시 걸리는 시간
        int[] time = new int[process_num + 1];
        // X 작업을 실행 완료하기까지 걸리는 시간
        int[] answer = new int[process_num + 1];
        // 선행 작업 수
        int[] in = new int[process_num + 1];

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();

        Queue<Integer> queue = new LinkedList<>();


        for (int x = 0; x <= process_num; x++) {
            list.add(new ArrayList<>());
        }

        for (int x = 1; x <= process_num; x++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            time[x] = Integer.parseInt(st.nextToken());

            int num=Integer.parseInt(st.nextToken());

            in[x]=num;

            if(num==0){
                answer[x] = time[x];
                queue.add(x);
            }

			// 사전 작업을 기준으로, 사전 작업을 수행 후 수행할 수 있는 것들을 list에 넣음
            for (int y = 0; y < num; y++) {
                int temp = Integer.parseInt(st.nextToken());

                list.get(temp).add(x);
            }
        }

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int z = 0; z < size; z++) {

                int now = queue.poll();


                for (int next : list.get(now)) {
                    in[next]--;

                    answer[next] = Math.max(answer[next], answer[now] + time[next]);
					
                    // 사전 작업이 모두 수행 완료되면 queue에 삽입
                    if(in[next]==0)
                        queue.add(next);

                }

            }
        }

        int max_answer=0;

        for(int candidate : answer){
            max_answer = Math.max(max_answer, candidate);
        }


        bw.write(String.valueOf(max_answer));
        bw.close();
        br.close();


    }




}

 

2) 다이나믹 프로그래밍

import java.io.*;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int process_num = Integer.parseInt(br.readLine());
        int answer=0;

        int[] dp = new int[process_num + 1];

        for (int x = 1; x <= process_num; x++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            int time,num;

            time = Integer.parseInt(st.nextToken());
            num = Integer.parseInt(st.nextToken());

            dp[x] = time;

            for (int y = 0; y < num; y++) {
                int temp = Integer.parseInt(st.nextToken());

                dp[x] = Math.max(dp[x], dp[temp] + time);
            }

            if(answer<dp[x])
                answer = dp[x];

        }

        bw.write(String.valueOf(answer));
        bw.close();
        br.close();


    }




}