[백준] 14567 선수과목 - DP

문제 링크 : https://www.acmicpc.net/problem/14567

🍊해결방법

• 선수과목이라는 특정 조건이 존재
• 선수과목을 리스트를 통해서 저장하자
• 과목 배열을 만들어서 해당 과목이 몇 학기 만에 끝나는지 저장하자
• 처음에는 과목 배열 모두 1로 초기화 (선수과목이 없는 과목도 있기 때문에)
• 1 ~ N 개의 과목을 다 보면서 해당 선수과목이 있는지 확인하고 있으면 +1 해서 최대값 갱신
• dp[num] = Math.max(dp[num], dp[i]+1)
• 최대값을 저장해야하는 이유는 같은 선수과목이 존재하게 되면 젤 오래 걸리는 과목이 끝나고서 해당 과목이 끝나는 거 이므로 최대값을 저장해야 한다

😀풀이

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

public class Main {

    static int N;
    static List<Integer>[] list;
    static int[] arr;


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 모든 전공과목 듣기, 선수과목 존재
        // 5초라서 시간 충분
        // 인접리스트 형태로 선수과목을 만들자
        // 과목 배열에 학기를 저장

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

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        list = new ArrayList[N+1];

        for(int i=1; i<=N; i++){
            list[i] = new ArrayList<>();
        }

        arr = new int[N+1];

        // M개의 선수과목 조건을 저장하자
        for(int i=0; i<M; i++){

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

            int pre = Integer.parseInt(st.nextToken());
            int later = Integer.parseInt(st.nextToken());

            list[pre].add(later);
        }

        Arrays.fill(arr, 1);

        for(int i=1; i<=N; i++){
            for(int j=0; j<list[i].size(); j++){

                int num = list[i].get(j);

                arr[num] = Math.max(arr[num], arr[i]+1);
            }
        }

        for(int i=1; i<=N; i++){
            System.out.print(arr[i]+" ");
        }

    }

}