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

문제 링크입니다: https://www.acmicpc.net/problem/11722

http://jaimemin.tistory.com/317와 비슷한 문제였습니다.

/*

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <cstring>

using namespace std;

 

const int MAX = 1000;

 

int N; //수열의 길이

int cache[MAX + 1], arr[MAX];

 

//arr[start]에서 시작하는 감소 부분 수열 중 최대 길이 반환

int LDS(int start) //Least Decreasing Sequence

{

        int &result = cache[start + 1];

        if (result != -1)

               return result;

       

        result = 0;

        for(int next=start+1; next<N; next++)

               if (start == -1 || arr[start] > arr[next]) //처음 index이거나 전보다 더 작을 경우에만

               {

                       int candidate = LDS(next) + 1;

                       if (candidate > result)

                              result = candidate;

               }

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N<1 || N>MAX)

               exit(-1);

 

        for (int i = 0; i < N; i++)

               cin >> arr[i];

 

        memset(cache, -1, sizeof(cache));

        cout << LDS(-1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략