2565번: 전깃줄

2565번: 전깃줄

사용 언어: C++

문제 요약

• 두 개의 전봇대 A, B 사이에 여러 개의 전깃줄이 연결되어 있음.
• 전깃줄은 A의 위치 번호와 B의 위치 번호 쌍으로 주어짐.
• 어떤 두 전깃줄이 교차한다면 위험하므로, 전깃줄 일부를 제거하여 서로 교차하지 않도록 만들고자 함.
• 남길 수 있는 최대 전깃줄 개수를 찾고,
  제거해야 할 전깃줄의 최소 개수를 출력하라.
• 입력
  • 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
• 출력
  • 첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

풀이

전깃줄 자체를 줄이는 방식이 아니라, A 위치를 중심으로 정렬을 한 후, B 위치끼리의 증가 관계만 유지하면 교차하지 않는 아이디어를 중심으로 푸는 것이다.

그래서 B위치들로 이루어진 수열에서 최장 증가 부분 수열 LIS(Longest Increasing Subsequence)를 구하고

전체 개수 - LIS 길이 = 제거해야할 최소 전깃줄 수가 된다.

그리고 이전 다이내믹 프로그래밍을 풀 때는 이중 for문을 사용했는데 이번에는 lower_bound + 이진 탐색으로 알고리즘을 수정해서 더 빠른 버전을 도입했다.

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

using namespace std;

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

    int n;
    cin >> n;

    vector<pair<int,int>> wires(n);

    for(int i=0; i<n; i++) cin >> wires[i].first >> wires[i].second;

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

    vector<int> b_wires(n);
    for(int i=0; i<n; i++)
    {
        b_wires[i] = wires[i].second;
    }

    vector<int> dp;
    for(int b : b_wires)
    {
    	// dp 안에 자기보다 큰 숫자 있는지 찾기
        auto it = lower_bound(dp.begin(), dp.end(), b);
        // 없었다면 자기가 가장 큰 숫자이므로 push_back
        if (it == dp.end()) dp.push_back(b);
        // b보다 크거나 같은 값 중 가장 왼쪽 값을 b로 교체
        else *it = b;
    }

    cout << n - dp.size() << '\n';

    return 0;
}