[2565] 전깃줄

문제 출처 : https://www.acmicpc.net/problem/2565

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

 

---

해당 문제는 처음에 Greedy로 접근을 하였다. 서로 겹치는 선 두개를 고려해 보면, 선들이 겹치지 않게 하기 위해서는 겹친 두 선 중 하나를 제거해야 하기 때문에 둘중에 더 많은 선을 교차하는 선분을 없애는 것이 당연하다. 따라서 전깃줄 중에 가장 많은 선과 겹쳐지는 선을 우선적으로 제거한다면 해답을 찾을 것이라고 생각하였다. 하지만 이 방식에서는 고려되지 않은 경우가 있었다. 물론 선이 두개만 존재한다면 답은 맞을 수 있겠지만, 여러개의 선분 중에서 많이 교차하는 선분을 고를때 제거 대상이 되는 선분이 여러개가 있다면, 어떤 것을 먼저 제거하느냐에 따라서 답이 달라 질 수 있다는 것이였다.

아래와 같은 입력을 생각해 보자.

5
1 3
2 1
3 5
4 2
5 4

[입력으로 주어진 전깃줄]

이런 경우 A의 1, 3, 4번이 총 2개가 겹쳐져 있다. 가장 많이 겹쳐져 있는 1, 3, 4중 먼저 제거하는 것에 따른 결과를 살펴보자.

1. A-1을 먼저 제거하는 경우

[총 2개의 선 제거가 필요하다]

2. A-3을 먼저 제거하는 경우

[총 2개의 선 제거가 필요하다]

3. A-4를 먼저 제거하는 경우

[총 3개의 선 제거가 필요하다]

 

1, 2와 달리 3의 경우에는 최종적으로 남는 전깃줄의 갯수도, 제거된 선의 수도 차이가 있다.

---

문제를 생각해보면 우리가 구하고자 하는 해답은 전깃줄이 겹치지 않게끔 하는 최소의 제거된 전깃줄의 갯수이다. 그리고 전깃줄이 겹치지 않는다는 것의 의미는 A 에서 B로 가는 전깃줄 연결에 대한 함수 f : A → B 를 정의할 때 함수 f가 주어진 정의역 A에서 단조 증가라는 말과 같다. (전깃줄을 제거했을 때 남은 \(i \in A \), \(f(i)=B_i\)에 대해 \(B_i\)가 증가수열이여야 한다)  총 전깃줄의 갯수는 고정되어 있으므로 제거할 최소의 전깃줄의 갯수를 구하는 문제는 뒤집으면, 가장 긴 증가하는 부분수열을 구하는 문제와 같다는 사실을 알 수 있다.

 

따라서 이 문제는 LIS를 푸는 일반적인 방식로 해결이 된다는 사실을 알 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    int n = 0, i = 0, j = 0;
    vector<pair<int, int>> dat;
    vector<int> d;
    
    cin >> n;
    d = vector<int>(n, 1);
    while(n--){
        cin >> i >> j;
        dat.push_back({i, j});
    }
    
    sort(dat.begin(), dat.end());
    
    for(i = 0; i < dat.size(); i++){
        for(j = 0; j < i; j++){
            if(dat[j].second < dat[i].second){
                if(d[j]+1 > d[i]){
                    d[i] = d[j] + 1;
                }
            }
        }
    }
    
    cout << dat.size() - (*max_element(d.begin(), d.end())) << "\n";
    
    return 0;
}