[백준 12015] 가장 긴 증가하는 부분 수열2 C++

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

 

이전까지 풀어봤던 LIS 문제들과 푸는 방법이 조금 다르다

기존LIS는 for문을 2번 돌려서 O(n^2) 시간안에 풀었다면

이번 문제는 수열의 크기가 N<= 1000000 이므로 O^2으로는 풀 수 없다.

그래서 log(n) 시간이 걸리는 이분 탐색 방법을 사용해야한다

 

LIS를 구하면서 만들어지는 배열은 반드시 오름차순으로 정렬 된 배열이기 때문에 이분탐색을 사용하면 효과적으로 LIS의 크기를 구할 수 있다

 

• 배열 마지막 수(arr.back())보다 새로운 수(arr[i])가 크다면 배열에 push 한다
• 그렇지 않다면 mylower_bound 함수를 사용해서 새로운 수 이상인 수가 처음 나온 인덱스를 찾아 해당 인덱스에 있는 기존 값은 arr[i]로 교체한다

이분 탐색을 위해 c++내장 함수인 lower_bound를 사용해도 되지만

공부를 위해서 mylower_bound를 따로 구현해서 풀어보았다!

---

• Ex) arr = {10, 20, 40, 25, 20, 50, 30, 70, 85}

처음 res배열 상태

10

 

arr[1]=20 은 10 보다 크기때문에 push한다

10

20

 

arr[2]=40 은 20 보다 크기때문에 push한다

10

20

40

 

arr[3]=25 는 40 보다 작기때문에 lower_bound를 실행하고, idx = 2 가 반환되므로 40이 25로 교체된다

10

20

25

 

arr[5]=50 은 25 보다 크기때문에 push한다

10

20

25

50

 

arr[6]=30 은 50 보다 작기때문에 lower_bound를 실행하고, idx = 3 이 반환되므로 50이 30으로 교체된다

10

20

25

30

 

arr[7]=75 는 30 보다 크기때문에 push한다

10

20

25

30

75

 

arr[8]=85 는 75 보다 크기때문에 push한다

10

20

25

30

75

85

이상 res 배열 만드는 과정이었습니다

 

#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<int> arr, res;
// key값 이상인 수 중에서 가장 먼저 나온 수의 인덱스를 반환
int mylower_bound(vector<int>& arr, int key){
    int st = 0;
    int ed = arr.size()-1;
    
    int mid = ed;
    
    while(ed > st){
        int mid = (st + ed)/2;
        if(key > arr[mid]){
            st = mid+1;
        }
        else{
            ed = mid;
        }
    }
    return ed;
}
 
void solve(){
    int cnt = 1;
    res.push_back(arr[0]);
    for(int i = 1; i < N; i++){
        if(res.back() < arr[i]){
            res.push_back(arr[i]);
            cnt++;
        }
        else{
            int idx = mylower_bound(res, arr[i]);
            res[idx] = arr[i];
        }
    }
    
    cout << cnt;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    arr.resize(N+1);
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    
    solve();
    
    return 0;
}
 

먼저 들어온 원소보다 lower_bound로 찾은 위치가 더 이전일 수 있기 때문임