[백준] 알고리즘 C++ 12015번 - 가장 긴 증가하는 부분 수열2

문제

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

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

소스코드

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int arr[1000001];
vector<int> v;
void bs(int num){
    int s=0;
    int e=v.size()-1;
    int ret=987654321;
    while(s<=e){
        int mid=(s+e)/2;
        if(v[mid]>=num){
            if(ret>mid){
                ret=mid;
            }
            e=mid-1;
        }
        else{
            s=mid+1;
        }
    }
    v[ret]=num;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    v.push_back(arr[0]);
    for(int i=1;i<n;i++){
        if(v.back()<arr[i]){
            v.push_back(arr[i]);
        }
        else{
            bs(arr[i]);
        }
    }
    cout<<v.size();
}

해설

기존 가장 긴 증가하는 부분 수열1에서는 dp를 이용해서 점화식을 i번째까지 가장 긴 증가하는 수열의 길이를 저장하였다.

하지만 이 방법은 O(n^2)의 시간복잡도가 걸리므로 이 문제에서는 n값이 백만이기에 절대로 시간내에 할 수가 없다.

그렇다면 우리는 더 빠른 방법을 찾아봐야한다.

 

우리는 가장 긴 증가하는 부분수열의 길이만 구하면된다. 그렇다면 기존 입력배열을 하나하나 살펴보는데 미리 전체의 배열 값을 안다고 생각하지말고 하나씩 입력이 들어올 때 현재 배열에서 뒤에 어떤 수가 오면 더 가장 긴 부분수열을 만들 수 있을가를 생각해봐야 한다.

즉, 마지막 요소가 무엇이 오면 더 유리한지 생각해봐야 한다.

10 20 10 30 20 50 의 입력이 주어졌을 때 생각해보자.

 

처음 아무것도 비교할게 없으니 당연히 처음입력 값이 길이의 순서중 첫번째로 들어가는게 맞다.

그렇다면 v라는 백터를 선언하였을 때 v의 마지막 요소는 10이 들어가있다.

이후 10뒤에 20이 오면 가장 긴 증가하는 부분수열은 2로 아까보다 1증가하였다. 그렇다면 백터에 20을 추가해주는게 증가 수열에 유리하다. 

하지만 이후 10이 오게된다면 기존의 백터에서 교체를 해야할게 살펴봐야한다. 왜냐하면 마지막요소가 클 수록 증가하는 수열을 방해하는 요소이기 때문이다. 그렇다면 우리는 여기서 lowerbound를 생각할 수 있다. 10보다 크거나 같은 요소가 어디에 위치한 인덱스인지 찾아봐야 한다는 것이다. 그렇다면 현재 10은 백터의 0번째 요소인 10의 위치와 바꿔줄 수 있다.

그다음으로 30이 오면 20보다 크기때문에 증가하는 수열을 하나 더 증가시켜 3이된다. 그렇다면 이는 유리한 조건이므로 백터에 추가해준다.

마지막으로 50을 추가하면 현재 백터의 마지막요소는 30이다. 그렇다면 가장 긴 증가하는 부분 수열을 4로 늘릴 수 있기에 증가시켜준다.

결국 마지막 요소가 어떤 값이 와야 유리한지를 생각하는게 이문제의 핵심이다.