[BJ] 1965: 상자넣기

       문제 요약        

- 문제

https://www.acmicpc.net/problem/1965

1965번: 상자넣기

 

 

- 입출력

파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

 

         아이디어        

 

현재 상자를 고려했을 때 최대 상자의 개수

따라서, 과거 이력을 확인하면서 (조건 : 나보다 크기가 작음)

가장 최대 상자의 개수를 구하면 된다

 

그리고, 현재 상자를 고려했을 때 상자 개수가 최대 상자 개수인지 확인해서 답을 구하면 된다

         소스코드        

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {//1965 상자 넣기
	static int N;
	static int[] cost;
	static int[] dp;
	public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine()); // 
        cost = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N ; i++) {
        	cost[i] = Integer.parseInt(st.nextToken());
        }
        
        dp = new int[N+1];
        int max = 0;
        // 증가하는 부분 순열
        for(int i = 1; i <= N; i++) {
        	dp[i] = 1;
        	for(int j = 1; j < i ; j++) {
            	if(cost[j] >= cost[i] || dp[i] >= dp[j]+1) continue;
        		dp[i] = dp[j]+1;
        	}
        	if(max<dp[i])max = dp[i];
        }
        System.out.println(max);
    }
}