[오늘의 문제] 상자 넣기

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

일렬로 늘어선 정육면체 모양의 상자들이 있습니다. 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있습니다.

예를 들어, 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면:

크기 1인 상자를 크기 5인 상자에 넣고, 이 상자를 크기 7인 상자 안에 넣을 수 있습니다.

또는 크기 1, 2, 3, 7인 상자를 순서대로 선택하여 총 4개의 상자를 한 개의 상자에 넣을 수 있습니다.

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

입력 형식
첫째 줄에 상자의 개수 n이 주어집니다. (1 ≤ n ≤ 1000)

둘째 줄에는 각 상자의 크기가 순서대로 주어집니다.

상자의 크기는 1,000을 넘지 않는 자연수입니다.

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

예제 입력 1
8
1 6 2 5 7 3 5 6
예제 출력 1
5
예제 입력 2
10
1 2 3 4 5 6 7 8 9 10
예제 출력 2
10

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

public class Main {
public static int maxNestedBoxes(int n, int[] boxes) {
// 각 위치에서 가능한 최대 상자 개수를 저장
int[] dp = new int[n];
Arrays.fill(dp, 1);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (boxes[j] < ____) {  // 현재 상자에 이전 상자를 넣을 수 있는지 확인
                dp[i] = Math.max(dp[i], ____);  // 최대 상자 개수 갱신
            }
        }
    }

    return ____;  // 가능한 최대 상자 개수 반환
}

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

    int[] boxes = Arrays.stream(br.readLine().split(" "))
                       .mapToInt(Integer::parseInt)
                       .toArray();

    System.out.println(maxNestedBoxes(n, boxes));
}

}

빈칸1: X
정답: boxes[i]
해설: 현재 상자(boxes[i])와 이전 상자(boxes[j])의 크기를 비교하여 이전 상자를 현재 상자에 넣을 수 있는지 확인합니다.
-> 나는 box[i-1]을 선택함 현재 상자(boxes[i]) 이전 상자(boxes[j]) 라는 개념을 인식 못한듯

빈칸2: X
정답: dp[j] + 1
해설: 이전 위치(j)까지의 최대 상자 개수에 현재 상자를 추가하므로 dp[j] + 1을 사용합니다.
-> 나는 dp[i] + 1 을 고름 이것도 마찬가지로 이전위치가 dp[j]라는 것을 인식못한듯 빨리 찍지 말고 좀 오래 읽고 생각해봐야 할 듯.

빈칸3: X
정답: Arrays.stream(dp).max().getAsInt()
해설: 모든 위치에서의 최대 상자 개수 중 가장 큰 값을 찾아야 하므로 Arrays.stream(dp).max().getAsInt()를 반환합니다.
-> 나는 dp[n - 1]을 선택함. max 보고 맞을거 같다는 생각은 했지만 stream 개념을 일단 잘 몰라서 안 고름.
Arrays.stream(dp): dp 배열을 IntStream으로 변환합니다.
.max(): IntStream에서 최댓값을 찾습니다.
반환 타입은 OptionalInt입니다. (값이 없을 수도 있기 때문)

getAsInt(): OptionalInt에서 실제 정수 값을 가져옵니다.
만약 OptionalInt가 비어 있다면 예외가 발생할 수 있습니다.