[백준 1965] 상자넣기

 

LIS 문제이다.

가장 큰 증가하는 부분 수열 문제와 답만 다를뿐 로직이 동일하다.

 

가장 긴 감소하는 부분 수열에 간단하게 풀이를 서술했다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[n];
        int dp[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int max = 0;
        for(int i=0; i<n; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(a[i] > a[j] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
            }
            if(max < dp[i])
                max = dp[i];
        }
        System.out.println(max);
    }
}