1965번 상자넣기

 기본적인 DP 문제(11053번, 11055번 문제와 같다).

 

 증가하는 부분 수열을 구하면 된다. 

 

 

#include <iostream>
#include <algorithm>
#define MAX 1001
 
using namespace std;
 
int N;
int A[MAX];
int cnt[MAX];
 
void solved(){
    for(int i=0;i<N;i++){
        cnt[i]=1;
        for(int j=0;j<i;j++){
            if(A[i]>A[j]){
                cnt[i]=max(cnt[i],cnt[j]+1);
            }
        }
    }
    
    int ans=0;
    
    for(int i=0;i<N;i++){
        ans=max(cnt[i],ans);
    }
    
    cout << ans << endl;
}
 
int main(){
    cin >> N;
    
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    
    solved();
}