(boj) 백준 gold5 14567 전제 조건(Java) – dp

(문제)

https://www.acmicpc.net/problem/14567

(설명)

각 과목의 in-degree를 계산하여 in-degree가 0이면 dp(i)에 1을 저장한다.
즉, 선수과목이 없기 때문에 첫 학기에 바로 수강할 수 있습니다.

dp(i) = k는 과정 i를 완료하는 데 필요한 최소 학기 수를 저장합니다.

5과목에 1-3-5, 4-5명의 플레이어 관계가 있는 경우 5과목을 이수하기 위한 최소 학기는 3학기입니다.

즉, 1과목부터 n과목을 순환하며 i과목을 선수과목으로 하는 j과목의 최소 학기는 Math.max(dp(i-1)+1, dp(j) ) .

(암호)

package dp;

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

public class boj_14567_선수과목 {
    static int n, m;
    static int() dp;
    static int() in;
    static List<Integer>() list;
    public static void main(String() args) throws Exception{
        //모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        in = new int(n+1);
        dp = new int(n+1); //dp(i) = k. i번 과목을 이수하기 위한 최소 학기
        list = new ArrayList(n+1);
        for(int i=0; i<=n; i++){
            list(i) = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int f = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            list(f).add(s);
            in(s)++;
        }

        for(int i=1; i<=n; i++){
            if(in(i)==0){
                dp(i) = 1;
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=0; j<list(i).size(); j++){
                int node = list(i).get(j);
                dp(node) = Math.max(dp(node), dp(i)+1);
            }
        }

        for(int i=1; i<=n; i++){
            System.out.print(dp(i) + " ");
        }
    }
    
}