백준 11722 가장 긴 감소하는 부분 수열 / C+

문제 : 11722

풀이 point

가장 긴 증가하는 부분 수열과 반대로 진행해주면 된다. i를 기준으로 j를 움직이며 arr[i]보다 큰 값이 있는지 확인한다.

풀이 방법

자세한 내용은 백준 11053 해설을 참고한다.

코드

//백준 11722, 가장 긴 감소하는 부분 수열

#include <iostream>
#include <algorithm>

int arr[1'000];
int dp[1'000];

int main (){

    int N;
    std::cin >> N;
    for(int i{0}; i<N; ++i) std::cin >> arr[i];

    for(int i{0}; i<N; ++i){
        for(int j{0}; j<i; ++j){
            if(arr[j] > arr[i]){
                dp[i] = std::max(dp[i], dp[j]+1);
            }
        }
    }

    std::cout << *std::max_element(dp, dp+N)+1;

    return 0;
}