[c++] 백준 2565 전깃줄 (dp / 최장 증가 부분 수열 / LIS)

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

솔루션

왼쪽 기준 오름차순으로 정렬했을때, 오른쪽 값이 이전보다 커야된다는 점에서 LIS임을 캐치 할 수 있었다.
정렬 후 오른쪽 기준의 최장 증가 부분 수열을 구한 후, 전봇대의 개수에서 빼주면 최소한으로 제거할 수 있는 전선의 개수를 구할 수 있다.
가장 긴 증가하는 부분 수열 문제와 코드가 아주 유사하다.

전체코드

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

using namespace std;

int n, dp[105];
vector<pair<int, int>> v;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }

    fill(dp, dp + n, 1);
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[i].second > v[j].second && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (res < dp[i]) res = dp[i];
    }
    cout << n - res;

    return 0;
}