[백준] 2568번 전깃줄 - 2 C++ 코드

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int n,x,y,res,b[100003];

vector<pair<int,int>> a;
vector<int> ress;
stack<pair<int,int>> stk;

int main() {
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> x >> y;
        a[i] = {x,y};
    }
    sort(a.begin(), a.end()); // first를 기준으로 정렬
    // 최대증가부분수열(lis, Longest Increasement Subsequence) 찾기
    for(int i = 0; i < n; i++) {
        auto k = lower_bound(b, b + res, a[i].second); 
        int pos_ = (k - b); // 인덱스 저장, 이후 몇 번째인지 알기 위해
        if(*k == 0) res++; // 0이라면 lis의 길이 1 증가
        *k = a[i].second; // lower_bound로 찾은 값대체 
        stk.push({pos_,a[i].first}); // 스택에 인덱스와 첫 건물 저장
    }
    int ret = (n - res); // 증가하지 않는 부분을 찾아줘야함
    cout << ret << '\n';
    res--; // LIS의 길이, index로 찾아야해서 -1
    while(stk.size()) {
        int f = stk.top().first;
        int s = stk.top().second;
        // 
        if(f != res) {
            ress.push_back(s); // 일치하지 않으면 삭제해야하는 건물
        } else {
            res--; // lis 값과 인덱스가 일치하면 res를 1 감소
        }
        stk.pop();
    }
    sort(ress.begin(), ress.end()); // 오름차순으로 출력
    for(int i : ress) cout << i << '\n';
    return 0;
}

 

최대증가부분수열 풀이로 해결할 수 있다. 문제에서 전깃줄이 교차하지 않게 하기 위해 없애야 하는 최소 개수를 구하라고 했다. 즉, 교차하지 않게 최대한 많은 전깃줄을 배치하는 방법을 찾으면 된다. 이 조건에서 연결된 건물 B에서 최대증가부분수열을 찾아주면 된다는 것을 도출할 수 있다. 전깃줄의 개수가 10만 이하이므로 O(n^2) 으로 해결할 수 없다. 따라서 lower_bound를 이용해서 res를 구해주었다.

없애야 하는 건물은, res - 1의 길이와 index가 일치하지 않은 경우를 찾아주었다. 이를 위해 stk에 lower_bound에서 찾은 인덱스와, 첫번째 건물의 값을 저장해주었다. res는 lis의 길이이고, 인덱스는 0부터 시작하므로 res에서 1을 감소시켰다. 그리고 stk의 위에서부터 하나하나 탐색하며 값이 일치하면 연결되어야 하는 전깃줄, 일치하지 않으면 제거해야 하는 전깃줄로 판단했다. 제거해야하는 전깃줄의 경우에는 ress에 넣어 오름차순 정렬을 한 후 출력을 했다.