[백준] 11053 - 가장 긴 증가하는 부분 수열 (C++)

문제 출처:

www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

문제 풀이:

• 필자가 생각하기에 이 문제의 핵심은 
  
  • 증가수열의 첫 부분 정하기
  • 뒷부분에서 만들어지는 증가 수열이 기존에 만들어진 증가수열의 일부분(중복되는 부분) 인지 체크
• 때문에 cache 자료구조를 만들어서 방문한 자리를 체크해주었다.
  • 이렇게 해주어도 괜찮은 이유는 예제를 보면서 알아보자
  • arr 10 20 10 30 20 50
    ret -1  -1  -1  -1  -1  -1
    일 때 처음 arr인 10이 들어가고 증가하는 함수를 찾는다.
  • arr 10 20 10 30 20 50
    ret  1   1    -1  1     -1  1
    이렇게 돌아서 10을 시작으로 돌았을 때 ans는 4가 된다.
  • 이후 20이 들어갔을땐 ret이 1이므로 함수가 돌지 않는다.
  • idx가 2인 10이 들어가면 -1이므로 함수가 실행되지만, 30이 이미 방문되어있기 때문에 30에서 끝난다.
  • 이렇게 해도 최대 길이를 구할 수 있는 이유는 맨 앞 idx보다 뒤에 있는 idx에서 시작해봤자 이미 앞 idx에서 증가수열을 이루면 어떤 방식으로 증가 수열이 이루어지더라고 뒤 idx로 시작한 증가수열이 더 작기 때문이다.
• 증가수열의 첫 부분은 그냥 처음부터 끝까지 다 돌려보았다.
• 그래서 그런지 python으로는 시간 초과가 났다. C++로 는 통과되었다.

#include <iostream>
#include <algorithm>

using namespace std;

int cache[1001];
int n;
int S[1001]={0,};

int get_maxLength(int start){
    int& ret = cache[start];
    if(ret!=-1)
    {
        return ret;
    }
    ret=1;

    for (int i =start+1;i<n;i++)
    {
        if(S[start]<S[i])
        {
            ret = max(ret,get_maxLength(i)+1);
        }
    }
    return ret;
}


int main()
{
    cin >>n;
    int temp=0;
    std::fill_n(cache,1000,-1);
    for(int begin=0;begin<n;begin++){
        cin >> temp ;
        S[begin]=temp;
    }
    int ans=0;
    for(int j =0;j<n;j++)
    {
        ans = max(ans,get_maxLength(j));
    }
    cout << ans <<endl;
    return 0;
}