전깃줄 C++ - 백준 2565

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

dp문제.

태그를 까고 나서 후회했다.

문제 접근

전깃줄이 겹치지 않는 조건은 어떤 전봇대에서 위치 $i$에 전깃줄이 반대편 전봇대에

연결되어 있을 때 위치 $i$ 전에 있는 전깃줄이 반대편에 위치된 곳보다

뒤에 위치해야 한다.

즉, 위치 $i$가 증가하면 연결 되어있는 전깃줄의 위치 역시 증가해야하고,

위치 $i$가 감소하면 연결 되어있는 전깃줄의 위치 역시 감소해야한다.

전깃줄이 겹치는 위치를 제거하려면 위 양상을 보이는 위치의 집합만을 남겨놓아야 한다.

따라서 최장 증가 부분 수열 (LIS) 를 찾고,

제거해야할 개수를 구하고, 출력한다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    int ans=1;
    int dp[501]; fill(dp+1,dp+501,1);
    vector<pair<int, int>> v(n);
    for(int i=0;i<n;i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(),v.end(),[](pair<int, int> l, pair<int, int> r)->bool{return l.first<r.first;});
    for(int i=1;i<n;i++) for(int j=0;j<i;j++){
        if(v[i].second>v[j].second) dp[v[i].second]=max(dp[v[i].second],dp[v[j].second]+1);        
        ans=max(ans,dp[v[i].second]);
    }
    cout << n-ans;
    return 0;
}