[백준 11722] 알고리즘 48일차 : 가장 긴 감소하는 부분 수열

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

11722번: 가장 긴 감소하는 부분 수열

동적계획법 C++

이번엔 감소하는 부분 수열이다.

 

접근 방법

가장 긴 증가하는 부분수열에서 감소하는 부분수열로 바뀌었을 뿐이다.

비교할때 이 점을 유의해서 비교하면 된다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n ;

    int num[n];
    int length[n];
    int max_length = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
        length[i] = 1;
        for(int j = 0 ; j < i ; j++){
            if(num[j] > num[i] && length[j] >= length[i]){
                length[i] = length[j]+1;
            }
        }
        if(max_length < length[i])
            max_length = length[i];
    }
    
    cout << max_length;
    return 0;
}