C++ 백준 11054 (가장 긴 바이토닉 부분수열)

백준 11054 (가장 긴 바이토닉 부분수열)

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

11054번: 가장 긴 바이토닉 부분 수열

---

LIS를 이용하는 문제이다.

또한 LIS의 길이만 알면 된당.

LIS의 길이에 대한 설명은 여기(링크)에 자세히 나와있으니 꼭 알고오자.

 

LIS의 길이를 구하는 방법은 O(N^2)과 O(NlogN)로 구하는 두 가지의 방법이 있는데 본 글에서는 O(NlogN)방법을 이용한다.

 

O(N^2)으로도 해봤는데 속도가 확실히 차이가 나는 것을 볼 수 있다.

밑에꺼가 O(N^2)이당

 

설명

---

예제에서 보면 답은 {1 5 2 1 4 3 4 5 2 1}와 같이 찾을 수 있다.

자세히 보면 계속 오름차순으로 가다가 어떤 한지점에서 계속 내림차순으로 진행된다.

당연하다. 그게 문제의 조건이니까!

 

그렇다면 해당 조건을 만족하는 수열의 최장길이는 어떻게 찾을까?

LIS를 이해하고 왔다면 바로 무엇인가 떠오를 것이다.

 

모든 지점에서 앞에서부터의 LIS의 길이와 뒤에서부터의 LIS길이를 합쳐봐서 가장 큰 값을 고르면 될 것 같다.

 

{1 5 2 1 4 3 4 5 2 1}

위 예제를 살펴보면 숫자 5가 기준일 때 왼쪽으로 부터 LIS길이와 오른쪽으로 부터 LIS의 길이의 합이 최대가 되는 것을 볼 수 있다. 때문에 답도 5가 기준일 때 길이가 답이다.

 

즉 앞에서부터 LIS를 진행하고 각 인덱스에 대한 LIS의 길이를 저장한 후 (org_dis) 

뒤에서부터 LIS를 진행해 다시 각 인덱스에 대한 LIS를 저장한다. (rev_dis)

 

그리고 각 인덱스에 대해 org_dis+rev_dis-1의 값이 가장 큰 수가 답일 것이다. (기준점은 중복 되니까 -1)

 

 

구현

---

LIS의 길이를 구할 때 O(N^2)로 구하는 법과 O(NlogN)으로 구하는 법이 있다고 했다.

밑 코드는 O(NlogN)방법을 이용하여 구현했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int card[50001];
int maxtmp_org[50001];
int maxtmp_rev[50001];
vector <int> L_org, L_rev;


int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>card[i];
    }
    
    for(int i=0;i<n;i++){
        if(i==0){
            L_org.push_back(card[i]);
            maxtmp_org[i]=1;
        }
        else{
            if(L_org[L_org.size()-1]<card[i]) L_org.push_back(card[i]);
            else *(lower_bound(L_org.begin(), L_org.end(), card[i])) = card[i];
            maxtmp_org[i]=L_org.size();
        }
    }

    for(int i=n-1;i>=0;i--){
        if(i==n-1){
            L_rev.push_back(card[i]);
            maxtmp_rev[i]=1;
        }
        else{
            if(L_rev[L_rev.size()-1]<card[i]) L_rev.push_back(card[i]);
            else *(lower_bound(L_rev.begin(), L_rev.end(), card[i])) = card[i];
            maxtmp_rev[i]=L_rev.size();
        }
    }


    int ans=0;
    for(int i=0;i<n;i++){
        ans = max(ans, maxtmp_org[i]+maxtmp_rev[i]-1);
    }

    cout<<ans;
    return 0;
}