BOJ 14567 java 풀이

DP 문제이다.

선수과목에서 숫자가 큰거보다 나중에 들어야하는 작은거는 없다.

작은거부터 큰거로 가면서 이전 선수과목 중 가장 기수가 높은거 + 1 해주면 된다.

그리고 그 과정에서 이 과목이 내꺼의 선수과목인지를 미리 체크해서 그걸 쓰면 됨

 

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        boolean[][] cond = new boolean[N+1][N+1];
        int[] dp = new int[N+1];
        
        for(int i=0; i<M; i++) {
            int b = sc.nextInt();
            int a = sc.nextInt();
            
            cond[b][a] = true;
        }
        dp[1] = 1; // 첫과목
        
        for(int i=2; i<N+1; i++) {
            for(int j=1; j<i; j++) {
                if(cond[j][i]) { // 이게 지금꺼 선수과목이면
                    dp[i] = Math.max(dp[i], dp[j]); // 이게 가장 많이 필요한건지 체크
                }
            }
            dp[i]++; // 거기서 한학기 더들으면 됨
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<N+1; i++) sb.append(dp[i] + " ");
        System.out.println(sb.toString());
    }
}