BOJ 11053번

#include <iostream>

#include <vector>

using namespace std;

vector<int> arr;

int dp[1010] = {};

int max(int a, int b){

    if(a > b) return a;

    else return b;

}

int main(){

    cin.tie(NULL);

    ios_base::sync_with_stdio(false);

    int n;

    int tmp;

    int m = 0;

    cin >> n;

    arr.push_back(0);

    for(int i = 1; i <= n; i++){

    cin >> tmp;

    arr.push_back(tmp);

    }

    for(int i = 1 ; i <= n; i++){

        int min = 0;

        for(int j = 0 ; j < i; j++){

            if(arr[i] > arr[j]){

                if(min < dp[j]){

                    min = dp[j];

                }

            }

        }

        dp[i] = min + 1;

        if(m < dp[i]){

            m = dp[i];

            }

        }

     cout << m;

     return 0;

}

우선 dp테이블 생성 후에 각각의 아이템까지의 증가 수열을 저장시킨다. 각각의 증가 수열을 알아내는 방법은 이때까지의 자신보다 작은 아이템의 수열중에서 가장 큰 수열에 +1 을 하여 새로 저장한다. 이때 +1은 자기자신이다. 우선 dp테이블 생성 후에 각각의 아이템까지의 증가 수열을 저장시킨다. 각각의 증가 수열을 알아내는 방법은 이때까지의 자신보다 작은 아이템의 수열중에서 가장 큰 수열에 +1 을 하여 새로 저장한다. 이때 +1은 자기자신이다.