백준 1965번 - 상자넣기

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

문제를 잘 읽다보면 증가하는 부분 수열의 길이를 물어보는 것을 알 수 있다.

지난 번에 풀었던 가장 긴 증가하는 부분 수열의 코드와 똑같다.

같은 문제여도 개념 자체를 묻는게 아니라

상자같이  문제를 응용해서 나오는 경우가 더 많기 때문에 

문제를 보면서 LIS에 대한 개념을 다시 이해하는 것도 중요한 것 같다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(){
    
    int n;
    cin>>n;
    
    vector<int> A(n,0);
    vector<int> dp(n,0);
    
    for(int i=0;i<n;i++)
        scanf("%d",&A[i]);
    
    int ans=0;
    for(int i=0;i<n;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(A[i]>A[j] && dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        }
        ans=max(ans,dp[i]);
    }
    
    cout<<ans<<endl;
    return 0;
}