[백준] 2565번 전깃줄

문제 링크: https://www.acmicpc.net/problem/2565

문제

입출력

문제 접근

dp문제이고, 가장 긴 증가 수열을 구하는 문제이다.

A전봇대를 오름차순으로 정렬해놓는다. 그러면 오른쪽에 있는 전깃줄이 자기마음대로 엉켜있다. 이때, 엉켜있는 것을 없애고, 최소로 전깃줄을 없애려면, b의 가장 긴 증가수열(LIS)를 구하면 된다.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
int cache[101];
int N;
vector<pair<int, int> > v;
int dp(int n){
    int& res = cache[n];
    if(res != -1) return res;
    res = 1;
    for(int i = n+1 ; i < N ; i++){
        if(v[n].second < v[i].second) res = max(res, dp(i)+1);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> N;

    for(int i = 0 ; i < N ; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        v.push_back(make_pair(temp1,temp2));
    }    
    memset(cache,-1,sizeof(cache));
    sort(v.begin(),v.end());
    int res = 0;
    for(int i = 0 ; i < N ; i++){
        res = max(res, dp(i));
    }
    cout << N-res << "\n";
}