[algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4

 

DP 문제이다.

순서대로 반복문을 돌다가 증가하는 부분을 확인하면서 값을 올리는 방식으로 풀면 된다.

// 가장 긴 증가하는 부분수열 4
#include <iostream>
#include <stack>
using namespace std;

int main(void){
    int count, answer = 1, dp[1001], arr[1001];
    stack<int> stack;
    cin >> count;
    for(int i = 0; i < count; i++){
        cin >> arr[i];
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(arr[i] > arr[j] && dp[i] <= dp[j]){
                dp[i] = dp[j] + 1;
                answer = max(answer, dp[i]);
            }
        }
    }
    cout << answer << "\n"; 
    for(int i = count - 1; i >= 0; i--){
            if(answer == dp[i]){
                stack.push(arr[i]);
                answer--;
            }
    }
    while(!stack.empty()){
        cout << stack.top() << " ";
        stack.pop();
    }
}