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

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

이분 탐색

---

1. 문제 해결 아이디어

 

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

 

위 문제에서 추가적인 요소만 넣어준다면 해결 할 수 있다!

 

위 문제에서 사용했던 이분 탐색의 방법으로는 현재 증가 부분수열 vector에 있는 원소들이 실제로 부분수열을 이루는 원소들이 아니다.

예를 들어 10 20 30 5 10 같은 입력이 주어졌다고 생각해보자

10

10 20 

10 20 30

여기까지는 순차적으로 증가하기 때문에 vector의 맨 뒤에 push해 줄 수 있었다.

다음 차례는 5가 들어올 차례이고 5는 10의 자리에 대신 들어간다

5 20 30

그리고 다시 10이 들어오면 10은 20의 자리에 대신 들어간다

5 10 30

 

결국 위와 같은 vector를 얻게 되는데 증가하는 부분수열의 길이인 3은 알 수 있지만 vector의 원소들이 실제로 구한 부분수열의 원소에 속하는가? 에 대한 답은 될 수 없다.

 

따라서 배열을 하나 더 만들어 줘서 현재 원소가 증가하는 부분수열의 몇 번째에 들어갈 수 있는 원소인지를 체크해줘야 한다.

 

10 20 30 5 10을 예시로 새로 만들 배열을 보면 

원소	10	20	30	5	10
순서	1	2	3	1	2

 

우리는 위 배열에서 부분 수열의 길이는 3임을 알 수 있었다.

따라서 새로 만든 배열의 뒷 부분부터 앞으로 탐색을 하면서 3번째 순서를 가진 원소(30)를 stack에 넣어준다.

3번째 원소를 찾았으므로 2번째 순서인 원소를 찾아야 한다.

그리고 20 (2번째원소)을 찾았기 때문에 stack에 넣어준다.

위 작업을 배열이 종료될때까지 반복해준다. (순서가 0인 원소는 없기때문에 다음에 찾을 순서가 0인 경우에 바로 끝내도 무방)

 

그리고 stack에 쌓여있는 원소들을 역순으로 출력해주면 원하는 증가하는 부분수열을 구할 수 있다.

---

2.  코드

#include <iostream>
#include <algorithm>
#include <vector>
 
#define pii pair<int, int>
 
using namespace std;
 
int N, cnt, resnum;
int arr[1000001];
 
vector<int> temparr, stk;
pii check[1000001];
 
 
void solve(){
    temparr.push_back(arr[0]);
    check[0] = {arr[0], 0};
    
    for(int i = 1; i < N; i++){
        if(temparr.back() < arr[i]){
            temparr.push_back(arr[i]);
            cnt++;
            
            check[i] = {arr[i], cnt};
        }
        else{
            int lbidx = lower_bound(temparr.begin(), temparr.end(), arr[i]) - temparr.begin();
            temparr[lbidx] = arr[i];
            
            check[i] = {arr[i], lbidx};
        }
    }
    
    cout << cnt + 1 << "\n";
    
    for(int i = N-1; i >= 0; i--){
        if(cnt == check[i].second){
            stk.push_back(check[i].first);
            cnt--;
        }
    }
    
    for(int i = stk.size()-1; i >= 0; i--){
        cout << stk[i] << " ";
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    
    solve();
    
    return 0;
}