백준 1965 - 상자 넣기 C++

문제

백준 - 상자 넣기

여러 상자의 크기가 주어질 때, 앞의 상자는 뒤의 상자가 크기가 더 커야지 들어갈 수 있습니다.

한 번에 넣을 수 있는 최대의 상자 개수를 구하는 문제입니다.

접근 방식

점점 상자의 크기가 커지면서 가장 긴 길이를 구하는 문제입니다. 그래서 LIS, 최장 증가 부분 순열 문제로 볼 수 있습니다.

풀이

LIS 문제는 DP를 이용한 N^2 방식과 이분 탐색인 N log N 복잡도로 풀 수 있습니다. 하지만 이 문제에서는 상자들의 최대 개수가 1000게라서 N^2로도 제한 시간인 2초내에 해결이 가능합니다.

코드

int max1 = 0;
dp[0] = 1;
for (int i = 1; i < N; ++i) {
    dp[i] = 1;
    for (int k = 0; k < i; ++k) {
        if (boxList[k] < boxList[i]) {
            dp[i] = max(dp[i], dp[k] + 1);
        }
    }
    max1 = max(max1, dp[i]);
}

cout << max1; // 한번에 담을 수 있는 최대 상자 개수 출력