[백준][c++] 12738번: 가장 긴 증가하는 부분 수열 3

문제 해석

주어진 수열 안에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 입니다.

 

풀이

1. 먼저, 숫자의 개수 N을 입력받습니다.
2. N개의 숫자를 입력받아 numbers 벡터에 저장합니다.
3. lis라는 벡터를 생성하고 첫번째 숫자를 추가합니다. 이 벡터는 가장 긴 증가하는 부분 수열을 저장하는 데 사용됩니다.
4. numbers 벡터의 두 번째 원소부터 마지막 원소까지 순회하며, 현재 숫자가 lis의 마지막 원소보다 크면 lis에 추가합니다. 이는 현재 숫자가 lis에 포함될 수 있음을 의미합니다.
5. 만약 현재 숫자가 lis의 마지막 원소보다 작다면, 현재 숫자가 들어갈 수 있는 lis 내의 위치를 이진 탐색으로 찾아서 그 위치의 값을 현재 숫자로 업데이트합니다. 이는 lis를 최대한 작은 값으로 유지하면서 길이를 늘리는 방법입니다.
6. lis의 길이를 출력합니다. 이 길이가 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이가 됩니다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int bs(vector<int>& list, int num){

    int left=0, right=list.size(), mid;
    while (left < right){
        mid = (left+right)/2;

        if(list[mid]<num)
            left = mid+1;
        else{
            right = mid;
        }
    }
    return right;
}

int main() {
    int n;
    cin>> n;
    vector<int> nums(n);

    for(int i=0;i<n;i++){
        cin>> nums[i];
    }

    vector<int> list;
    list.push_back(nums[0]);

    for(int i=1;i<n;i++){
        if(list.back() < nums[i]){
            list.push_back(nums[i]);
        }
        else{
            int idx = bs(list, nums[i]);
            list[idx] = nums[i];
        }
    }

    cout<<list.size();

    return 0;
}