BJ1965 상자 넣기

https://www.acmicpc.net/problem/1965
사용한 알고리즘 : DP
난이도 : 실버 2

문제

앞의 상자의 크기가 뒤의 상자의 크기보다 작을 때, 앞의 상자를 뒤에 상자 안에 넣을 수 있다.

상자의 순서와 갯수가 주어질때, 한 번에 넣을 수 있는 최대의 상자 개수를 구하시오.

문제 접근 방법

DP 알고리즘으로 문제를 해결하기 위해서는 다음의 2 조건을 만족해야한다.
1. 큰 문제를 같은 구조의 작은 문제로 분해할 수 있다.
2. 작은 문제의 최적의 해를 이용해서 큰 문제의 최적의 해를 구할 수 있다.

위의 두 경우를 만족하면 문제를 점화식의 형태로 만들어 풀 수 있다.

점화식

• N번에 위치한 상자에 담는 경우
  - 1번부터 N-1까지의 상자중에서 N번보다 크기가 작고 가장 많은 상자를 담은 상자를 N번 상자에 담는다.

코드

package Java.Y22.M03.D04;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ1965_BoxInBox {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dp[i] = 0;
		}
		
		int answer = 0;
		for(int i = 1; i < N; i++) {
			for(int j = 0; j < i; j++) {
				if(arr[i] <= arr[j]) continue;
				if(dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
				}
			}
			
			if(dp[i] > answer) answer = dp[i];
		}
		
		System.out.println(answer + 1);
		
	}

}