[알고리즘]Algospot_LIS

출처 : https://www.algospot.com/judge/problem/read/LIS

문제

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.

어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.

출력

각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.

정답코드

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int longestSeq(vector<int>& v, vector<int>& c, int pos)
{
    //이 코드를 추가해줬더니 정상 작동. why?
    if(pos+1==v.size()) return 1;

    int &ret = c[pos+1];

    if(ret != -1) return ret;
    
    ret = 1;

    for(int i = pos+1; i<v.size(); i++)
    {
        if(pos == -1 || v[pos] < v[i])   ret = max(ret, 1 + longestSeq(v,c,i));
    }

    return ret;
}

int main()
{
    FASTio;

    int t;

    cin >> t;
    
    while(t--)
    {
        int n;

        cin >> n;

        vector<int> v(n, 0);
        vector<int> c(n, -1);

        for(int i=0; i<n; i++)
            cin >> v[i];
        
        cout << longestSeq(v,c,-1)-1 << endl;

        cout << endl;
    }

    return 0;
}

풀이 및 사고과정

이 문제에서 많은 시간을 할애했다.
일단 문제를 이해하는데에 조금 시간이 걸렸고
결국엔 책을 참고했는데 DP를 활용하는 부분이 이해가 안돼서 시간이 걸렸고
책과 거의 유사하게 코드를 쳤는데 정답이 안돼서 시간이 걸렸다.
이 문제도 나중에 한 번 더 봐야되는 문제인듯하다