[BOJ] 상자넣기

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다.

예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다.

하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

풀이

마스료시카처럼 상자를 중첩해서 넣고 그 최대의 갯수를 구하는 문제이다.

넣을 수 있는 상자의 최대 갯수를 구해야 하므로 상자의 크기는 점점 커져야 한다.
이중 가장 큰 갯수의 값이 되어야 하므로 LIS(최장증가부분수열) 을 구하는 문제이다.

LIS구현 방법은 크게 DP와 바이너리 서치가 있다.
아래의 방법을 참고하길 바란다.
LIS

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int[] dp = new int[N];
        dp[0] = 1;
        int answer = 0;
        for(int i = 1; i < N; i++) {
            for(int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }

                if (dp[i] == 0) {
                    dp[i] = 1;
                }
            }
            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EC%83%81%EC%9E%90%EB%84%A3%EA%B8%B0