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

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

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

for문을 반대로 쓰는게 살짝 헷갈렸는데 가장 긴 증가하는 부분수열이랑 똑같이 풀어주면 된다

#include <bits/stdc++.h>

using namespace std;
int n;
int dp[1001] = {0}, a[1001] ={0};

int main(void) {
    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> a[i];
        dp[i] = 1;
    }

    for(int i=n-1; i>=1; i--){
        for(int j=n;j>i;j--){
            if(a[i]>a[j])
                dp[i] = max(dp[i], dp[j]+1);
        }
    }

    int result = 0;
    for(int i=1; i<=n; i++)
        result = max(result, dp[i]);
    cout << result << endl;

    return 0;
}