백준 02565 - 전깃줄

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

2565번: 전깃줄

 

고려사항

- lis 알고리즘 활용

- <int, int> 로 벡터에 넣은 후, first 기준으로 정렬 => 0 - n-1 까지의 인덱스를 지닌 v.second 를 하나의 수열이라 여김.

- 최대 증가 수열 길이를 구하고 n-ans 를 해줌.

 

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

vector<pair<int, int>> v;
int n, ans = -1;
int memo[101];

int main() {
    int from, to;
    cin>>n;

    for(int i=0;i<n;++i){
        cin>>from>>to;
        v.push_back({from, to});
    }
    sort(v.begin(), v.end());

    for(int i=0;i<n;++i){
        memo[i] = 1;
        for(int j=0;j<i;++j){
            if(v[j].second < v[i].second){
                memo[i] = max(memo[i], memo[j]+1);
            }
        }
        ans = max(ans, memo[i]);
    }

    cout<<n - ans;
    return 0;
}