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

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

BOJ - 가장 긴 증가하는 부분 수열 2

문제 유형: LIS(Longest Increasing Subsequence), 다이나믹 프로그래밍, 이진 탐색

난이도: Gold II

시간 제한: 1초

메모리 제한: 512MB

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

매 arr[i]마다 lis배열에 lower_bound()를 통해서 arr[i]보다 크거나 같은 요소의 위치를 찾아서 그 자리를 대체한다. 만약 arr[i]가 제일 크다면 새로 맨 뒤에 추가한다.

이것이 실제 lis가 아님에 유의하자.

우리가 이 lis를 통해 알 수 있는 것은 lis의 맨 마지막 요소가 실제 lis의 맨 마지막 요소는 맞다는 것이고, lis의 크기가 실제 lis의 크기라는 것이다.

실제 lis배열을 알고싶다면, https://riveroverflow.tistory.com/entry/BOJ-1400-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-5

[BOJ] 1400 - 가장 긴 증가하는 부분 수열 5

을 참고하자.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

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

  vector<int> lis;
  for (int i = 0; i < n; ++i) {
    auto it = lower_bound(lis.begin(), lis.end(), arr[i]);

    if (it == lis.end()) {
      lis.push_back(arr[i]);
    } else {
      *it = arr[i];
    }
  }

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

  return 0;
}