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

 

 

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

접근 방식

 

가장 긴 증가하는 부분 수열 문제와 같지만 조건이 다르다

N이 1000에서 1,000,000으로 바뀌어서 기존에 N제곱이 걸리는 코드로 푼다면 시간초과가 뜬다

 

따라서 이분탐색과 함께 lower bound를 활용해 문제를 푼다면 O(nlogn)으로 더 빠르게 문제를 해결할 수 있다

 

C++에서는 lower_bound 함수를 제공하는데 이는 이분탐색으로 배열을 탐색하면서 특정 값 이상이 처음 나오는 위치를 찾는 함수이다.

따라서 임의의 LIS라는 빈 배열을 두고

A배열을 순회하면서 현재 요소를 LIS 배열에 삽입할 위치를 찾는다

만약 그 위치가 LIS 배열의 끝이라면 요소를 추가하고

아니라면 해당 위치의 값을 현재 요소로 대체한다

 

최종적으로 LIS 배열의 길이가 정답이 된다

 

실제로 arr = [10, 20, 10, 30, 20, 50] 일 때,

1. LIS = []
2. 첫 번째 숫자 10: LIS = [10]
3. 두 번째 숫자 20: LIS = [10, 20]
4. 세 번째 숫자 10: LIS = [10, 20] (lower bound로 10 위치에 값 유지)
5. 네 번째 숫자 30: LIS = [10, 20, 30]
6. 다섯 번째 숫자 20: LIS = [10, 20, 30] (lower bound로 20 위치 유지)
7. 여섯 번째 숫자 50: LIS = [10, 20, 30, 50]

다음과 같이 동작하게 된다

 

 

코드

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

int main() {
    int N; cin>>N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin>>A[i];

    vector<int> LIS;

    for(auto n : A) {
        auto pos = lower_bound(LIS.begin(), LIS.end(), n);
        if(pos == LIS.end()) LIS.push_back(n);
        else *pos = n;
    }

    cout<<LIS.size();
}