(C++) - 백준(BOJ) 2565번 : 전깃줄

www.acmicpc.net/problem/2565

2565번: 전깃줄

dp(lis) 문제였습니다.

 

풀이방법

 1. a, b가 pair형태로 저장되는 vector v변수를 선언 후 n개의 젓깃줄 정보를 입력받습니다.

 2. a를 기준으로 sort해줍니다.

 3. 교차하지 않으려면 봐야할 정보는 1가지 입니다. 이미 a는 오름차순으로 정렬되어 있으니 b만 연속해서 오름차순으로 되어 있는지, 그 길이는 몇인지 확인하면 됩니다. 

 4. n - 길이가 답이고 이를 출력합니다. 

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,ans;
vector<pair<int, int>> v;
vector<int> d;
int main(){
    cin >> n;
    d.resize(n, 1);
    for(int i = 0; i < n; i++){
        int a,b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    
    sort(v.begin(), v.end());
    
    for(int i = 0; i < v.size(); i++){
        for(int j = 0; j < i; j++){
            if(v[j].second < v[i].second){ // b가 증가 형태로 연결되어있으면
                if(d[j]+1 > d[i]){ //
                    d[i] = d[j] + 1;
                }
            }
        }
    }
    
    for(auto x : d) ans = max(ans,x);
    cout << n - ans <<'\n';
}