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

문제

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

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

문제 해결

1. 가장 긴 증가하는 부분 수열과 비슷하게 현재 자기 자신의 길이를 dp [i]에 저장했다.

2. A = {10, 30, 10, 20, 20, 10}인 경우에서 가장 긴 감소하는 부분 수열은 30, 20 , 10이다.

3. 처음 10은 뒤에 숫자가 없으므로 자동으로 dp[0] = 1이다.

4. 그다음 30은 자기 뒤로부터 숫자가 자기 자신(30) 보다 크면 dp[i],dp[j] 를 비교한다.

5. 이 방법을 끝까지 반복한다.

 

코드

#include <iostream>
using namespace std;
int main(void){
    int dp[1001];
    int ary[1001];
    int N,Max = -1;
    cin >> N;
    for(int i = 0;i<N;i++){
        cin >> ary[i];
    }
    dp[0] = 1;
    int temp = 0;
    for(int i = 1;i<N;i++){
        for(int j = i;j>-1;j--){
            if(ary[i]<ary[j]){
                if(dp[j]>temp){
                    dp[i] = dp[j]+1;
                    temp = dp[j];
                    Max = max(Max,dp[i]);
                }
            }
        }
        if(temp == 0){dp[i] = 1;}
        temp = 0;
    }
    cout << Max;
}