[BOJ 2568번/C++] 전깃줄

코딩 테스트 문제를 푸는 초보 블로그 주인의 과정에 대한 글입니다. 이 솔루션은 효율적인 솔루션이 아닐 수 있으며 많은 부정확성을 포함할 수 있습니다. 개선할 점이 있다면 댓글로 남겨주세요!

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

전원 코드 – 2

설명

예제 입력은 다음과 같습니다.

1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

A로 정렬

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

문제는 { 1, 8 }, { 3, 9 }, { 4, 1 }을 교차할 선의 예로 제시했습니다. 자르지 않은 행을 A 위치를 기준으로 정리하면 {2, 6, 7, 9, 10}이 됩니다. 어디선가 본 규정 아닌가요?

예. 이 문제는 최장 증가 서브 시퀀스 응용 문제입니다.

가장 긴 증가하는 하위 시퀀스를 찾으면 해당 시퀀스는 자르지 않은 상태로 두어야 하는 와이어입니다. 따라서 이들을 제외하고 나머지 전선은 곧 절단해야 할 전선입니다.

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

#define endl '\n'

using namespace std;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<pair<int, int>> lines(N);
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        lines(i) = { a, b };
    }
    sort(lines.begin(), lines.end());

    vector<int> nocut;
    vector<int> idx;
    nocut.push_back(lines(0).second);
    idx.push_back(0);
    int len = 1;
    for (int i = 1; i < N; i++) {
        if (nocut(len - 1) < lines(i).second) {
            nocut.push_back(lines(i).second);
            idx.push_back(len);
            len++;
        }
        else {
            vector<int>::iterator pos = lower_bound(nocut.begin(), nocut.end(), lines(i).second);
            *pos = lines(i).second;
            idx.push_back(pos - nocut.begin());
        }
    }
    cout << N - len << endl;

    vector<int> cut_idx;
    for (int i = idx.size() - 1; i >= 0; i--) {
        if (idx(i) == len - 1) {
            len--;
            continue;
        }
        cut_idx.push_back(i);
    }

    for (int i = cut_idx.size() - 1; i >= 0; i--) {
        cout << lines(cut_idx(i)).first << endl;
    }

    return 0;
}