접근

A 와 B 사이에 전깃줄이 있는데 이것들을 교차하지 않도록 만들려한다.
모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야하는 전깃줄의 최소 개수를 구하면 된다.

전깃줄의 개수는 100 이하 자연수고 A와B의 범위는 500이하의 자연수다.

이것도 최장길이수열로 비슷하게 풀었는데 현재 값들보다 작은 값들을 확인하면서 그 값들+1 한것들중 가장 큰값을 현재값으로 정해가면서 마지막까지 하면된다.
그리고 꼬이지 않는 선에서 가장 많이 있는 선을 N 에서 뺴게 되면 뺴야 해야할 선의 수가 나오게 되는것이다.

코드

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

int N,ret=-987654321;
vector<pair<int, int>> v;
int dp[504];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N;
    
    for(int i=0;i<N;i++) {
        int start,end;
        cin >> start >> end;
        v.push_back({start,end});
    }
    
    sort(v.begin(), v.end());
    
    
    for(int i=0;i<N;i++) {
        for(int j=0;j<i;j++) {
            if(v[i].first>v[j].first and v[i].second>v[j].second) {
                dp[i]=max(dp[j]+1,dp[i]);
                ret=max(ret,dp[i]);
            }
        }
    }
    
    cout << N-(ret+1) << "\n";
    
    return 0;
}