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

algorithm : dp

 

해설 

가장 긴 증가하는 부분 수열과 매우 흡사한 문제이다. 가장 긴 증가하는 부분 수열 와 차이점은 if(arr [i] < arr [j]) 이 부분

으로 바꾸고 제출하면 답이 나온다

 

가장 긴 증가하는 부분 수열 : https://tedcho.tistory.com/31?category=950876

#include<bits/stdc++.h>
#define LM 1000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N;
int arr[LM];
int dp[LM];
int ans;

void input(){
    scanf("%d",&N);
    for(int i = 1 ; i <= N ; i++){
        scanf("%d",&arr[i]);
    }
}

void DP(){
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j < i ; j++){
            if(arr[i] < arr[j]) dp[i] = max(dp[i],dp[j] + 1);
        }
        ans = max(ans,dp[i]);
    }
    printf("%d",ans + 1);
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    return 0;
}