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

BOJ 12015 - 가장 긴 증가하는 부분 수열 2 (https://www.acmicpc.net/problem/12015)

 

01. 🔎 문제 탐색

N: 수열 A의 크기 (1 <= N <= 1e6)

* 주어진 수열 A에서 가장 긴 증가하는 부분 수열을 구하는 문제

01-1. 가능한 시간 복잡도

• N의 최대 크기가 1e6으로 시간 복잡도 O(N log N) 이하로 구현 가능

01-2. 알고리즘 선택

• 수열 A를 1회 반복하며, 이분 탐색을 통해 부분 수열을 찾으면 O(N log N)의 시간 복잡도는 가짐

02. 📝 코드 설계하기

1. 수열의 크기 N과 수열의 원소 N를 차례대로 입력
2. 원소 입력 시, 부분 수열 배열(lis)에 해당 원소를 이분 탐색
       2-1. 탐색하여 나온 index가 부분 수열 배열의 크기와 같은 경우, 새로운 원소로 추가
       2-2. 아닐 경우, 나온 index의 부분에 현재 원소로 대체
           (Greedy| 더 작은 원소로 대체하는 것으로, 현재 부분 수열의 최대 길이를 유지하면서
           뒤에 등장할 부분 수열의 길이가 더 길 경우 갱신할 수 있음) 
3. 부분 수열 배열(lis)의 크기 출력

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

int lower_bound(vector<int>& lis, int target){
  int left = 0, right = lis.size();
  while(left < right){
    int mid = (left + right) / 2;

    if(lis[mid] < target) left = mid + 1;
    else right = mid;
  }

  return left;
}

int main(){
  cin.tie(0) -> sync_with_stdio(0);

  int N;
  cin >> N;
  
  vector<int> lis;
  for(int i = 0, el; i < N; i++){
    cin >> el;

    int pos = lower_bound(lis, el);

    if(pos == lis.size()) lis.push_back(el);
    else lis[pos] = el;
  }

  cout << lis.size() << "\n";

  return 0;
}