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

 

매일 한 문제씩 알고리즘 푸는 스터디.. 약간 구몬 느낌으로 문제 받아서 풀고있다. 저번에는 DP문제를 줘서 풀만했는데 이번에는 LIS라는 듣도보도 못한 알고리즘을 들고와서 힘들었음ㅠ

 

이리저리 검색해보니 LIS는 최장 증가 수열.. 숫자가 증가하는 부분 수열을 구하는 알고리즘 같다. 완전탐색으로 하면 2^n이 걸리고 DP를 쓰면 N^2이 걸린다. 이분탐색을 써서 최적화를 할 수 있다고는 하는데 이건 나중에 풀어보던가 해야지. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);
    
    vector<int> v(n);
    vector<int> dp(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
        
    int max = 0;
    
    for (int i = 0; i < n; i++)
    {
        if (dp[i] == 0)
            dp[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (v[i] > v[j])
            {
                if (dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
            }
        }
        
        if (max < dp[i])
            max = dp[i];
    }
    
    cout << max;
    
    return 0;
}

 

다른 사람 코드 참고하면서 풀었는데 일단 dp는 최장 문자열 길이를 저장하는 것 같다, dp[i]는 i 인덱스의 최장 부분 배열 길이인 것 같고..

 

이걸 i 보다 작은 배열을 전부 확인해서 증가하는 부분을 발견한다면 길이를 증가시킨다. 

 

어엄.. 그렇다.. 완벽하게 이해한 건 아님