[#2565] 전깃줄

/* 
A에 연결된 위치 번호를 기준으로 정렬한다.
전선 꼬이지 않으려면 B에 연결된 위치 번호가 증가하는 수열이여야 한다.
따라서 B 위치 번호의 LIS를 구한다
구한 LIS는 연결된 전선의 갯수이고 출력해야 하는 것은 없애야 하는 전선의 갯수이기때문에
n-LIS를 출력한다.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    
    vector<pair<int,int>> connect(100);
    vector<int> dp(100);
 
    for (int i = 0; i < n; i++){
        cin >> connect[i].first >> connect[i].second;
    }
 
    sort(connect.begin(), connect.begin() + n);  //A를 기준으로 정렬
    
    //B의 LIS 구하기
    dp[0] = 1;
 
    for (int i = 1; i < n; i++) {
        int maxVal = 0;
        for (int j = 0; j <= i - 1; j++) {
            if (connect[j].second < connect[i].second)
                maxVal = max(maxVal, dp[j]);
        }
        dp[i] = maxVal + 1;
    }
 
    int LIS = INT_MIN;
 
    for (int i = 0; i < n; i++) {
        LIS = max(LIS, dp[i]);
    }
 
    cout << n - LIS;
 
    return 0;
}

 

A를 기준으로 정렬해서 하자! 까지는 생각했지만 B의 LIS를 구해야한다까지 생각이 못갔다...