[BOJ] 2565 전깃줄/Dynamic Programming/이분 탐색/최장 증가 부분 수열(LIS)/C++ 풀이

문제

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

2565번: 전깃줄

 

풀이

예제

문제에서 제시해준 예제를 통해 풀이를 생각했다.

위 처럼 전깃줄 개수가 처음에 주어지고 그 다음 (시작 전봇대 위치 - 끝 전봇대 위치)들이 주어진다.

시작 위치 기준으로 정렬한다면 다음과 같이 된다.

이 때 문제의 예시의 답에서 알려준 끝 전봇대 위치가 1, 8, 9인 전깃줄을 제외하고 관찰해보면 흥미로운 특징이 보인다. 바로 2, 4, 6, 7, 10은 증가하는 수열이라는 것이다.

시작 전봇대는 증가하는 순서로 정렬 된 상태이므로 끝 번호 또한 증가하는 상태라면 전깃줄이 교차하지 않을 것이다. 따라서 시작 전봇대 번호순으로 정렬한 후 끝 전봇대 번호 수열에서 증가하는 부분 수열의 최대 길이가 전깃줄이 교차하지 않을 때의 최대 전깃줄 수 이다. 

 

결국 문제는 최장 증가 부분 수열의 길이를 구하는 것이다.  

 

길이 N의 수열에 대하여 최장 증가 부분 수열의 길이는 다음과 같이 구할 수 있다.

(0 <= i < N)일 때, D[i]는 길이가 (i+1)인 부분 증가 수열 중 가장 작은 마지막 값을 저장한다고 하자.

 

예를 들어, 

[2, 1]

위의 수열에 대하여 길이가 1인 부분 증가 수열은 {2}와 {1}이 있다. 각 수열에서 마지막 값은 각각 2,1이고 이중 가장 작은 값은 1이다. 따라서 D[1] = 1이다. 

 

수열을 A라고 할 때 A[i]에 대해 D[i]를 갱신한다.

만약 D[i - 1]의 값보다 A[i]의 값이 크다면 D[i] = A[i]로 갱신할 수 있다. 왜냐하면 D[i - 1]의 값은 길이가 i - 1인 부분 증가 수열의 마지막 값인데 A[i]가 이 값보다 크니 길이가 i인 부분 증가 수열의 마지막 값은 A[i]가 될 수도 있는 것이다. 물론 갱신 이전의 D[i]의 값이 A[i]보다 작다면 갱신할 수 없다.

 

문제의 예시를 통해 이해 해보자.

시작 전봇대 번호 기준으로 정렬한 후 끝 전봇대 번호 수열은 8, 2, 9, 1, 4, 6, 7, 10이다. 배열 D는 각 값을 최소값으로 갱신할 것이므로 무한대로 초기화 한다. 

 

 

i = 0

D배열을 탐색하며 8이 들어갈 수 있는 가장 왼쪽의 위치를 찾는다. D[0]을 8로 갱신한다.

D[0]의 의미는 "길이가 1인 부분 증가 수열들 중에서 가장 작은 '마지막 값'"이다. 

 

 

i = 1

 D배열의 값은 전부 2보다 크다. 따라서 D[0]을 2로 갱신한다.

 

 

i = 2

 

9는 2보다 크다. 따라서 길이가 1이고 끝 값이 2인 부분 증가 수열 뒤에 9를 붙여 길이가 2인 부분 증가 수열을 완성할 수 있는 상태다. 그러므로 D[1] = 9로 갱신한다.

 

i = 3

1은 길이가 1인 부분 증가 수열들의 마지막 값 중 최소값이다. 따라서 D[0] = 1로 갱신한다.

 

i = 4

4는 길이가 2인 부분 증가 수열들의 마지막 값 중 최소값이다. 따라서  D[1] = 4로 갱신한다.

 

 

i = 5, 6, 7

차례대로 길이가 3, 4, 5인 부분 수열을 완성시킬 수 있는 수다. 따라서 아래와 같이 값을 갱신한다.

 

결국 D = {1,4,6,7,10, INF, INF, INF}로 완성된다.

부분 증가 수열의 길이는 결국 5가 최대임을 알 수 있다.

참고로 D는 값이 오름차순으로 유지되고 있으므로 A[i]의 값이 들어갈 위치를 찾을 때 이분탐색으로 빠르게 알 수 있다.

그러므로 길이 N인 수열에 대하여 O(NlogN)의 시간 복잡도로 최장 증가 부분 수열의 길이를 구할 수 있다.

 

C++ 풀이

https://github.com/seung-gwang/algorithm-ps/tree/main/%EB%B0%B1%EC%A4%80/Gold/2565.%E2%80%85%EC%A0%84%EA%B9%83%EC%A4%84

algorithm-ps/백준/Gold/2565. 전깃줄 at main · seung-gwang/algorithm-ps

#include <iostream>
#include <vector>
#include <algorithm>
#define INF (999999999)
using namespace std;

int main() {
    int N;
    vector<pair<int, int>> lines;

    cin >> N;
    for (int i = 0; i < N; ++i) {
        int s, e;
        cin >> s >> e;
        lines.push_back({ s, e });
    }

    sort(lines.begin(), lines.end());
    vector<int> A;

    for (const auto& e : lines) {
        A.push_back(e.second);
    }

    vector<int> D(A.size(), INF);
   
    for (const int a : A) {
        int l = 0;
        int r = A.size() - 1;

        int idx = 0;
        while (l <= r) {
            int mid = (l + r) / 2;

            //a보다 큰 D[i]값 중 가장 작은 것 (가장 왼쪽에 있는 것)
            if (D[mid] >= a) {
                idx = mid;
                r = mid - 1;
                
            }
            else { //D[mid] < a
                l = mid + 1;
            }
        }

        D[idx] = D[idx] > a ? a : D[idx];
    }

    int incrementLen = 0;
    for (const int d : D) {
        if (d != INF) {
            incrementLen++;
        }
    }

    cout << N - incrementLen;

    return 0;
}