Computer Science & Engineering

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

풀이

    이 문제는 이전 글에서 다루었던 가장 긴 증가하는 부분 수열(https://shyeon.tistory.com/52)에서 사용한 DP를 이용할 경우 시간 복잡도가 O(n^2)이  걸리므로 이 문제의 최대 길이인 10^6이 주어질 경우 10^12으로 시간제한인 1초를 훌쩍 넘게 된다. 따라서 이 문제는 O(N * log N)이 걸리는 알고리즘 방식을 이용해야한다.

    이 알고리즘은 가장 현재까지 탐색한 수열 중 가장 긴 수열의 길이를 가진 배열을 항상 유지한다. 만약 배열의 맨 마지막 원소 즉 가장 큰 값보다 클 경우 배열 맨 뒤에 붙여준다. 그렇지 않을 경우 현재 위치의 원소가 그 배열에서 위치할 수 있는 곳을 이진탐색을 이용하여 찾고 그 위치의 원소와 바꾼다. 예시를 이용하여 다시 설명하겠다.

예제

위 예제를 풀이한 알고리즘 순서대로 풀어보겠다. 처음 원소는 음수의 무한대로 초기화한다. 따라서 

1. -INF
2. -INF 10 (맨 끝에 추가)
3. -INF 10 20 (맨 끝에 추가)
4. -INF 10 20 (10자리에 10이 들어갈 수 있음)
5. -INF 10 20 30 (맨 끝에 추가)
6. -INF 10 20 30 (20 자리에 10 교체)
7. -INF 10 20 30 50 (맨 끝에 추가)

위의 예시는 반복되는 숫자가 있으므로 다른 예시로 한 번 더 해보겠다.

예시 : 10 20 40 30 70 90 50 60 80

1. -INF
2. -INF 10
3. -INF 10 20
4. -INF 10 20 40
5. -INF 10 30 40
6. -INF 10 30 40 70
7. -INF 10 30 40 70 90
8. -INF 10 30 40 50 90
9. -INF 10 30 40 50 60
10. -INF 10 30 40 50 60 80

이런 식으로 진행된다. 따라서 마지막 크기에서 -1을 해주면 가장 긴 수열의 길이를 구할 수 있다. 마지막에는 가장 긴 수열이 저장되는 것은 아니지만 길이는 이 방법을 이용하여 O(N log N)으로 구할 수 있다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MN = 1001;
const int INF = 1e9; //무한대

vector<int> dp;

int main() {
    int N; cin >> N;
    dp.push_back(-INF); //마이너스 무한대 push
    for(int i = 0; i < N; i++) {
        int a; cin >> a; //입력 받아서
        if(dp.back() < a) { //배열의 맨 마지막 원소보다 크면 뒤에 저장
            dp.push_back(a);
        }
        else { //그렇지 않을 경우
            auto it = lower_bound(dp.begin(), dp.end(), a); // 이진탐색을 이용하여 들어갈 수 있는 위치 탐색
            *it = a; //해당 위치에 교체
        }
    }

    cout << dp.size() - 1; // -무한대 빼고 길이 출력
}

채점 결과