[백준][C++] 12015번: 가장 긴 증가하는 부분 수열 2 <213>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

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

생각의 흐름

이번 문제는 기존의 LIS 를 구하는 DP 방식만으로는 시간안에 해결할수가 없었다.

 

나또한 처음에 어떻게 해야 시간을 줄일 수 있을지 생각하지 못해 다른 블로그의 글을 참고하였다.

기존의 LIS 풀이와 거의 유사하지만, 저장할때 방식이 조금 달라진다!

 

vec[i]는 길이가 i인 배열에서 가장 큰 수를 저장해주면 된다.

 

문제의 예시를 사용해 보자.

10, 20 ,30, 25, 15, 60

 

알고리즘의 탐색 과정은 다음과 같다.

[1] vec가 비어있거나, vec의 마지막 값이 삽입되려는 값보다 작을때 vec에 삽입한다.

[2] 1번의 경우가 아니라면, lower_bound를 통해 해당 위치의 값을 삽입하려는 값으로 치환한다.

 

0. vec에 가장 최소의 값을 미리 너어준다. 나는 INT_MIN 를 추가해 주었다. 

vec : [INT_MIN]

우선은 가장 작은 수를 vector에 삽입해 준 후, 이후 부터 input과 비교를 해줄 것 이다.

 

1. vec[1]에 10이 저장된다. INT_MIN보다 10이 크기 때문이다.

vec : [INT_MIN, 10]

 

2. vec[1] < 20 이므로, vec[2]에 20이 저장된다.

vec : [INT_MIN, 10, 20]

 

3. vec[2] < 30 이므로, vec[3]에 30이 저장된다.

vec : [INT_MIN, 10, 20, 30]

 

4. vec[3] > 25 이므로, 부분 수열의 길이는 증가될 수 없다. vec[3]의30을 25로 치환해준다.

좀더 정확하게는 lower_bound(25)를 통해 25보다 큰 수중 가장 작은 수 인 30의 위치를 찾아 치환한다.

vec : [INT_MIN, 10, 20, 25]

(길이가 4인 부분 수열중 가장 큰 수가 30에서 25로 변경된다.)

이런 식으로 부분수열의 마지막 수가 계속 작아져야 부분수열의 길이가 증가 할 수 있다.

 

5. vec[3] > 15 이므로, 부분 수열의 길이를 증가시킬 수 없다. vec[2]의20을 15로 치환한다.

vec : [INT_MIN, 10, 15, 25]

이때 치환해줄 20의 위치를 찾기 위해 이진탐색(이분탐색)을 구현해도 되지만, Lower_bound를 사용해도 된다.

 

6. vec[3] < 60 이므로, vec[4]에 60이 저장된다.

vec : [INT_MIN, 10, 15, 25, 60]

최종적으로 vec는 [INT_MINT, 10, 15, 25, 60]을 저장하게 된다.

 

여기서 정답인 LIS의 길이는 우리의 vec의 size 에서 1을 빼주면 된다.

우리는 맨 처음 초기값을 위해 INT_MIN을 추가해 줬었다. 이 부분을 빼줘야 한다!

 

 

나의 코드

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

int N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    vector<int> vec;
    vec.push_back(INT_MIN);
    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;

        if (vec.back() < num) {
            vec.push_back(num);
        } else {
            const vector<int>::iterator &iter = lower_bound(vec.begin(), vec.end(), num);
            *iter = num;
        }
    }

    cout << vec.size() - 1;

    return 0;
}