[C/C++] 징검다리 /소프티어/ DP / LIS

소프티어 징검다리 문제 

 

입력예제1

 

5 3 2 1 4 5

 

출력예제1

 

3

 

---

징검다리 풀이 

이 문제는 최장 증가 부분 수열 알고리즘을 이용해서 풀이를 하는 문제이다. 

 

최장 증가 부분 수열 알고리즘(LIS)이란?

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.

 

LIS 알고리즘에는 DP 알고리즘을 사용하는 것이 유리하다. 

아래 방식처럼 전체의 값을 1로 정의하고 만약 원래 값보다 체크하는 값이 크다면 max를 써서, 값을 새로 넣어주는 식으로 정의할 수 있다. 

for (int k=0; k<n; k++){
	length[k] = 1;
	for (int i=0; i<k; i++){
		if(arr[i] < arr[k]){
			length[k] = max(length[k], length[i] + 1);
		}
	}
}

 

처음에는 이 문제를 재귀함수를 써서 사용을 했는데, 시간 복잡도가 O(2^n)이 나와서 시간초과가 떠버렸다. 

 

그래서 DP로 바꾸고 문제를 푸니 훨씬 빠르게 문제를 해결할 수 있었다. 

 

---

징검다리 코드 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> vec;
int result = 0;
int n;
int dp[3001];
int value[30001];

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    int min;
    for(int i = 0 ; i< n; i++){
        int num;
        cin >> num;
        vec.push_back(num);
        dp[i] = 1;
    }
    
    for(int i = 0; i < n-1; i++){
        for(int j =i; j< n; j++){
            if(vec[i] < vec[j] && dp[i] >= dp[j]){
                dp[j] = dp[i] + 1;
            }
        }
    }
    for(int i = 0; i< n; i++){
        result = max(result, dp[i]);
    }
    
    cout << result;
   return 0;
}