[백준] 상자넣기

참고 : www.acmicpc.net/problem/1965

1965번: 상자넣기

아주 좋은 풀이 링크를 보고 풀었다. 갓.. (m.blog.naver.com/occidere/220788208204)

 

- dp 문제

- LIS 개념을 알면 잘 풀 수 있었던 문제. 좋은 거 배웠당.

- DP[i] : 1부터 i까지 최대로 감쌀 수 있는 박스 갯수 (증가 수열 갯수)

 

 

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

public class Solution {

    private static int n;
    private static int[] box;
    private static int[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        box = new int[n+2];
        dp = new int[n+2];
        int max = 0;
        for (int i = 1; i <= n; i++) {
            box[i] = sc.nextInt();
            dp[i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if(box[j] < box[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}