[백준 2568] 전깃줄 - 2

 

 DP 문제다. 문제를 보다 보면 스토리를 만들어둔 LIS 문제임을 알 수 있다. 전깃줄을 A 전봇대와 연결되는 위치 순으로 정렬해서, B 전봇대에 연결되는 위치를 기준으로 LIS를 찾는 것과 같은 맥락이니까.

 

[백준 12015] 가장 긴 증가하는 부분 수열 2 (tistory.com)

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

 

[백준 14003] 가장 긴 증가하는 부분 수열 5 (tistory.com)

[백준 14003] 가장 긴 증가하는 부분 수열 5

 

 예전에 풀었던 LIS 문제들과 거의 유사하게 구현해서 풀었다. 생각을 확장하는 순서를 간단하게 정리해보자면 다음과 같다.

 

1. LIS를 O(n log n)에 구현하는 로직을 떠올린다. 각 원소가 "길이가 인덱스인 LIS의 가장 마지막 값"을 나타내는 DP 배열을 이용하면 된다. 만약 DP의 가장 마지막 원소보다 새로 탐색 중인 값이 크다면, DP 배열에 새로운 마지막 원소로 추가하고, 아니라면 lower_bound를 찾아 기존 DP값을 갱신한다(같은 길이의 LIS라면 끝값이 더 작을수록 유리하므로, lower_bound를 찾아 갱신하는 것은 최소한 손해보지 않는 선택이다).

 이 과정을 끝마치면 DP의 크기가 최종적으로 완성된 LIS의 길이가 된다.

 

2. LIS의 구성을 알아내려면 역추적 할 수 있는 정보가 필요하다. 입력 받는 배열들이 LIS를 이룰 때, 몇 번째 원소 뒤에 붙게 되는 지를(본인 바로 앞에 놓이는 원소의 원래 배열 내 인덱스) 알 수 있다면 쉽게 추적할 수 있다.

 위의 로직에서 새로운 값이 DP 배열에서 제자리를 찾아들어가 특정 길이의 LIS를 이룰 때, 이는 본인이 이루는 특정 길이-1인 LIS에 본인이 붙는 것과 같은 선택이다. 그러므로 과정 중에 각 길이의 LIS 끝 값의 인덱스를 따로 저장해두고 이를 조회해서, 본인 바로 앞에 놓이는 원소의 원래 배열 내 인덱스를 저장하는 prev 배열을 채워나갈 수 있다. 만약 본인이 갱신하게 된 DP 인덱스가 길이 1짜리 LIS를 나타내는 인덱스라면, 본인이 가장 앞에 놓임을 뜻할 수 있게 -1 등으로 표기해둔다. 

 1번의 과정에 더해서, DP의 과정의 가장 마지막 원소보다 새로 탐색 중인 값이 크다면, prev[탐색 중인 값의 인덱스]를 LIS 인덱스 배열의 가장 끝 값(현재까지 형성된 가장 긴 LIS의 끝 원소 인덱스 값)로 저장하고, LIS 인덱스 배열의 가장 끝에 새로 탐색 중인 인덱스를 집어 넣어준다. 그렇지 않다면, prev[탐색 중인 값의 인덱스]를 위에서 설명한 로직에 맞게 더 길이가 1 짧은 LIS의 마지막 인덱스로 저장하고, 본인이 갱신한 LIS 인덱스 배열 또한 갱신해준다.

 이 과정을 끝마치고, LIS 인덱스 배열의 가장 끝 값부터(최종적으로 완성된 LIS의 마지막 원소의 인덱스) prev 배열을 역추적 해나가며 LIS 구성을 찾아낸다.

 

3. 위 문제에서는 제거해야 하는 전깃줄 수와 그 번호를 묻고 있다. 따라서 LIS 자체를 출력하는 것이 아닌, LIS에서 제외된 원소들을 출력해야 한다. 2번 과정에서 LIS 구성을 찾아 낼 때, 그 구성하는 전깃줄의 A 전봇대와 연결되는 위치들을 Set에 저장해둔다. 그리고 모든 전깃줄 배열(A 전봇대와 연결된 위치를 기준으로 오름차순 정렬된 상태)을 탐색하며, A 전봇대와 연결된 위치 값이 LIS Set에 포함되는지 확인하고 포함되지 않는 전깃줄만 출력한다. 제거된 전깃줄 수는 기존 전깃줄 수에서 LIS Set의 원소 수를 빼면 간단하게 구할 수 있다.

 

 LIS 알고리즘 자체가 생소하다면 풀기 힘든 문제라서, 다양한 알고리즘을 접하면서 새로 공부하거나 계속 리마인드하는 것이 중요하다고 다시 한 번 느끼게 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#define a first 
#define b second  

using namespace std;

typedef pair<int, int> connection;

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

    int n, aNum, bNum;
    vector<connection> connectionList;

    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> aNum >> bNum;
        connectionList.push_back({aNum, bNum});
    }

    sort(connectionList.begin(), connectionList.end());

    vector<int> dp;
    vector<int> lisInd;
    vector<int> prev(n, -1);

    dp.push_back(connectionList[0].b);
    lisInd.push_back(0);

    for(int i=1; i<n; i++) {
        if(dp[dp.size()-1] < connectionList[i].b) {
            prev[i] = lisInd[dp.size()-1];
            dp.push_back(connectionList[i].b);
            lisInd.push_back(i);
        } else {
            auto lb = lower_bound(dp.begin(), dp.end(), connectionList[i].b);
            *lb = connectionList[i].b;
            lisInd[lb-dp.begin()] = i;
            if(lb-dp.begin()>0) {
                prev[i] = lisInd[lb-dp.begin()-1];               
            }
        }
    }

    unordered_set<int> lis;
    for(int i=lisInd[lisInd.size()-1]; i!=-1; i=prev[i]) {
        lis.insert(connectionList[i].a);
    }

    cout << connectionList.size()-lis.size() << "\n";
    for(auto con: connectionList) {
        if(lis.find(con.a)==lis.end()) {
            cout << con.a << "\n";
        }
    }

}