백준 2565(전깃줄) c++

문제

2565번: 전깃줄

n개의 전깃줄이 주어지면 전깃줄이 겹치지 않게 주어진 전깃줄을 최소로 제거해야 되는 문제입니다.

즉, 최소로 제거할 전깃줄의 개수를 구하는 문제입니다.

예를 들어 왼쪽의 그림처럼 전깃줄이 주어진다면

<1, 8>, <3, 9> , <2, 2>를 제거하거나

<1, 8>, <3, 9>, <4, 1>를 제거하면 모든 전깃줄이 엉키는 부분이 없어집니다.

즉, 3개의 전깃줄을 제거하면 됩니다.

일단 입력부분을 보면 알겠지만, A부분의 전깃줄이 오름차순으로 차례대로

주어지지 않습니다. 

그리고 전깃줄의 시작점을 A라 하고, 끝점을 B라 하면 끝점이 오름차순으로 주어져야

전깃줄이 엉키지 않습니다.

 

 

따라서 일단 A점으로 주어지는 전깃줄을 오름차순으로 정렬하고, A의 순서에 따라 B점의 수열이 주어지면 

B의 수열에서 부분 오름차순 중 가장 긴 수열을 찾으면 그 점들이 엉키지 않는 점입니다.

그럼 그 점의 갯수에서 n을 빼면 우리가 제거해야할 전깃줄의 개수입니다.

위의 예시를 보면 A점을 기준으로 오름차순 정렬하면 아래와 같습니다.

<1, 8>

<2, 2>

<3, 9>

<4, 1>

<6, 4>

<7, 6>

<9, 7>

<10, 10>

여기서 B점에서 가장 긴 부분수열을 구하고 n에서 빼면 정답이 됩니다.

vector<pair<int, int>> p;
int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        p.push_back({l, r});
    }

    sort(p.begin(), p.end());

pair의 first가 A점이고, second가 B점입니다.

A점을 기준으로 먼저 오름차순으로 정렬해줍니다.

int dp[101];
int cnt = 1;
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; j--)
        {
            if (p[i].second > p[j].second)
                dp[i] = max(dp[i], dp[j] + 1);
        }
        cnt = max(cnt, dp[i]);
    }
    cout << n - cnt;

정렬된 순서대로 가장 긴 증가하는 부분수열을 구하는 문제입니다. 해당 문제는 이미 풀어서 참고했습니다.

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
vector<pair<int, int>> p;
int dp[101];
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        p.push_back({l, r});
    }

    sort(p.begin(), p.end());
    int cnt = 1;
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; j--)
        {
            if (p[i].second > p[j].second)
                dp[i] = max(dp[i], dp[j] + 1);
        }
        cnt = max(cnt, dp[i]);
    }
    cout << n - cnt;

    return 0;
}