백준 2565 전깃줄 / C++

문제 : 2565

풀이 point

전기줄이 겹치지 않게 최소로 삭제할 수 있는 개수를 구하는 문제이다. 다시 생각해보면 최소로 삭제란 지금 현재 값을 가지고 가장 최대로 전기줄을 교차하지 않도록 두는 것이다.
즉, 최소로 삭제한다는 것은 가장 최대로 전기줄을 교차하지 않도록 하는 것과 같다는 것이다.

그러기 위해서는 A에 입력을 받는 전기줄의 번호를 정렬한 후 B에 입력된 숫자들을 가장 긴 증가하는 부분 수열을 구하면 된다.

풀이 방법

가장 긴 증가하는 부분 수열을 구한 후 N에서 빼면 최소로 삭제하는 전깃줄 수가 나온다.

코드

//백준 2565, 전깃줄

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

std::vector<std::pair<int, int>> vec;
int dp[501];

int main (){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N;
    std::cin >> N;
    for(int i{0}; i<N; ++i){
        int a, b;
        std::cin >> a >> b;
        vec.push_back({a, b});
    }

    std::sort(vec.begin(), vec.end());

    for(int i{0}; i<N; ++i){
        dp[i] = 1;
        for(int j{0}; j<i; ++j){
            if(vec[i].second > vec[j].second){
                dp[i] = std::max(dp[i], dp[j]+1);
            }
        }
    }

    std::cout << N - *std::max_element(dp, dp+N);

    return 0;
}