[백준 c++] 1965 상자넣기

---

문제

https://www.acmicpc.net/problem/1965
n개의 상자의 크기가 주어진다.
앞에 있는 상자가 뒤에 있는 상자보다 작으면 넣을 수 있다.
한 번에 넣을 수 있는 최대의 상자 개수를 출력해라.

---

풀이

가장 긴 증가하는 부분 수열 문제 랑 똑같은 문제다 🤧

dp[i]에는 내가 넣을 수 있는 상자의 최대 개수를 저장한다.
이 최대 개수는 앞에 나온 상자들 중에 나보다 크기가 작으면서 dp가 최대인 값이다.

입력이 다음과 같을 때,

1 3 2 4 5

• 크기 1인 상자는 나 자신만 담을 수 있다.
  dp[0] = 1
• 크기 3인 상자는 앞에 나온 상자를 담을 수 있다.
  dp[1] = dp[0] + 1 = 2
• 크기 2인 상자는 앞에 나온 상자 중에 크기 1인 상자를 담을 수 있다.
  dp[2] = dp[0] + 1 = 2
• 크기 4인 상자는 앞에 나온 상자 중에 크기가 작으면서 dp가 최대인 dp[2]를 담을 수 있다.
  dp[3] = dp[2] + 1 = 3
• 크가 5인 상자는 앞에 나온 상자 중 크기가 작으면서 dp가 최대인 dp[3]을 담을 수 있다.
  dp[4] = dp[3] + 1 = 4

🚨 주의할 점
맨 마지막에 나온 dp값이 정답이 아니다.
중간 중간 dp의 max값을 체크해줘야 한다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, k, a[1001], dp[1001], mx, ret;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        mx = 0;
        for (int j = i - 1; j >= 1; j--)
        {
            if (a[j] < a[i])
                mx = max(mx, dp[j]);
        }
        dp[i] = mx + 1;
        ret = max(dp[i], ret);
    }

    cout << ret << "\n";
}