[백준 1965] 상자 넣기 (DP) (C/C++)

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int arr[1010];
int dp[1010];
int Max;
 
int solve(int cnt)
{
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
    
    dp[cnt] = 1;
 
    for(int i = cnt-1; i >= 1; i--)
    {
        if(arr[cnt] > arr[i])
        {
            dp[cnt] = max(dp[cnt], solve(i) + 1);
        }
    }
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B1965_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    
    for(int i = N; i >= 1; i--)
    {
        Max = max(Max, solve(i));
    }
    
    cout << Max;
    
    return 0;
}