[LIS (가장 긴 증가하는 부분 수열) / BOJ 11053 / C++] 가장 긴 증가하는 부분 수열

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

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

모르면 한도끝도 어려운 LCS 문제! DP에 속하지만 따로 분류해서 공부하도록한다.

 

우선 O(N^2) 풀이부터 풀어보자.

 

이 부분은 코드 이해가 어려워서 그림으로 표현해봤다.

 

 

 

우선, 이 문제는 값을 저장할 배열 arr과, 현재 LCS 상태를 저장하는 cnt 배열이 필요하다.

값 하나를 볼때마다 LCS를 계속 업데이트해가면 된다.

 

특정위치 미만에서 나올 수 있는 가장 큰 LCS를 계속 저장해간다는 게 중요하다!!

 

#include <bits/stdc++.h>

using namespace std;

int N, arr[1001], maxValue, cnt[1001], res;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 0 ; i < N ; i++) {cin >> arr[i];}
    
    for(int i = 0 ; i < N ; i++){
        maxValue = 0;
        for(int j = 0 ; j < N ; j++){
            if(arr[i] > arr[j] && cnt[j] > maxValue){
                maxValue = cnt[j];
            }
            
            cnt[i] = maxValue + 1;
            
            res = max(res, cnt[i]);
        }
        
    }
    
    cout << res << '\n';
    
    
}