[c++/백준] 2565번: 전깃줄*

문제 링크

2565번: 전깃줄

풀이

LIS(최장 증가 부분 수열)을 이용하는 DP문제

1. 먼저 첫번째 전깃줄을 기준으로 오름차순 정렬을 한다.
2. 정렬된 전깃줄의 두번째 전깃줄 배열의 최장 증가 부분 수열을 구한다.
   2-1. 이 수열이 겹치지 않는 전깃줄의 최대수가 될테니 n에서 빼주면 답이 나온다.
   2-2. 입력값이 크지 않기 때문에 O(n^2)의 dp로 푼다. 현재 전깃줄의 dp를 1로 초기화해준 뒤, 이전 전깃줄보다 현재 전깃줄이 크다면 dp 값을 비교해 갱신한다.
3. 그렇게 dp의 최대값을 구해 n에서 빼면 된다.

코드

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

int main()
{
    int n;
    cin >> n;

    vector<vector<int>> v(n, vector<int>(2));
    for (int i = 0; i < n; i++)
    {
        cin >> v[i][0] >> v[i][1];
    }
    sort(v.begin(), v.end());

    vector<int> dp(n);
    int remove = 0;
    for (int i = 0; i < n; i++) // 현재 
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++) // 이전
        {
            if (v[j][1] < v[i][1])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        remove = max(remove, dp[i]);
    }

    cout<<n-remove<<endl;

    return 0;
}