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

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS 알고리즘 :: http://www.crocus.co.kr/583

이전에는 항상 _lower_bound를 제작하여 lis를 코딩하였다면 이번에는 vector와 std::lower_bound를 이용하여 코딩해보고자 한다.

LIS 알고리즘 원리는 위의 링크에서 확인하길 바란다.

벡터와 std::lower_bound를 쓰면 더 간결하게 해결되는 것은 자명하다.

auto it = lower_bound(lis.begin(), lis.end(), vc[i]) - lis.begin()의 의미는 결국

lis 벡터 내에서 vc[i]보다 크거나 같은 값의 이터레이터를 찾아 lis.begin()을 빼주면 auto it는 인덱스로 변하게 된다.

따라서 그 인덱스 lis[it]에 vc[i]를 넣어줌으로써 lis 길이를 구하는 알고리즘을 구현 할 수 있게 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <iostream> #include <cstdio> #include <algorithm> #include <vector>   using namespace std;   vector<int> vc;   const int MAX = 1000001; int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);         vc.push_back(val);     }       vector<int> lis(n + 1, MAX);            for (int i = 0; i < n; i++)     {         auto it = lower_bound(lis.begin(), lis.end(), vc[i]) - lis.begin();         lis[it] = vc[i];     }       int cnt = 0;     for (int i = 0; i < n; i++)         if (lis[i] != MAX)             cnt++;       printf("%d", cnt);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus