[백준] 1965번 상자넣기

문제 링크: https://www.acmicpc.net/problem/1965

문제

입출력

문제 접근

dp문제이다. 그리고 단순히 LIS(최장 증가 수열)을 적용하면 되는 문제이다.

코드 구현(c++)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int cache[1001];
int box[1001];
int N;

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

    
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        cin >> box[i];
    }
    int maxNum = -1;
    for(int i = 0 ; i < N ; i++){
        cache[i] = 1;
        for(int j = 0 ; j < i ; j++){
            if(box[j] < box[i]){
                cache[i] = max(cache[i], cache[j] + 1);
            }
        }
        maxNum = max(maxNum, cache[i]);
    }
    cout << maxNum << "\n";
}