백준 1965번 상자넣기

우선 증가하는 부분수열 문제를 dp로 풀수 있다면 이 문제또한 쉽게 풀수 있을것이다.
애초에 앞의 상자보다 값이 작으면 뒷 상자에 넣을수 있다는 조건이, LIS 문제의 정의와 같다.
다만 주의해야 할 점은, if 조건문에서 단순히 이전값이 현제 인덱스의 값보다 작을시, 이전 dp값에 +1한 것을 현재dp값에 더해주는것을 가능하게하는 조건으로 작용하는 것이 아니라,(아래의 코드에서 dp[i]=dp[j]+1 부분) 이전 dp의 값+1 한 것이 현재 dp의 값보다 커야한다라는 조건도 있어야 된다는 것이다.
나도 처음에 이 조건이 왜 필요한지 생각하느라 애를 참 많이 썼는데,
간단히 설명하자면

이전 값이 현재의 값보다 더 작다는 조건에 만족하는 중복된(같은수)를 카운트하는것을 방지하기 위한 장치이다.
  

예를 들면 1 5 2 2 3 7 이라는 값이 주어졌을때, dp값 조건을 주지 않으면 2를 2번 카운트 해 버린다. 3의 dp값이 4가 되버림.

 

또한 dp 문제에서는 각 dp 인덱스 값이 무엇을 의미하는지가 가장 중요한데, 여기 dp[i]의 의미는 i번째 수가 증가하는 부분수열의 일부이고, 몇번째 값인지, 앞에서부터의 순서이다. 이해가 잘  예를들면 dp[2]의 값이 2이다면, 3번째로 입력된  2라는 수가 "증가하는 부분수열의 일부분일때, 앞에서부터의 순서는 2번째" 라는 뜻이다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        int n=s.nextInt();
        int[] arr=new int[n];
        int[] dp=new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=s.nextInt();
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i]&&dp[j]+1>dp[i]){
                    dp[i]=dp[j]+1;
                }
            }
        }
        int max=dp[0];
        for(int a:dp){
            max=max>a?max:a;
        }
        System.out.println(max);

    }
}