[ BOJ 백준 12015번 - 가장 긴 증가하는 부분 수열 2 ] 해설 및 코드

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

목적

LIS(longest increasing subsequence, 최장 증가 부분 수열)의 길이를 구하자.

 

접근법

1. 이분탐색을 이용하여 NlogN의 복잡도로 LIS를 구한다.

2. LIS에 원소를 오름차순으로 삽입하는데, 이전 LIS의 가장 큰 원소보다 큰 원소가 주어지는 경우에만 삽입하여 길이를 늘린다.

3. 그렇지 않으면, LIS의 원소를 갱신한다.(갱신 가능한 경우는 기존 원소보다 크기가 작은 경우이다.)

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;cin>>n;
    vector<int> v;
    while(n--){
        int num;cin>>num;
        int pos=lower_bound(v.begin(), v.end(), num)-v.begin();
        if(pos==v.size())v.push_back(num);
        else if(v[pos]>num)v[pos]=num;
    }
    cout<<v.size();
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.