[C++] 백준 2565 - 전깃줄

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

2565번: 전깃줄

<알고리즘 분류>

   - 다이나믹 프로그래밍(Dynamic Programming)

 

<풀이> 

   예제 입력 1을 참고하여, x축은 전봇대 A에서 나가는 전깃줄, y축은 전봇대 B의 전깃줄을 표시해 봤다. 백준 사이트의 예제 입력을 보면서 이 그림을 보면 된다. 

  자, 이렇게 정리하면 B전봇대 기준에서의 수열은 [8, 2, 9, 1, 4, 6, 7, 10] 이다. 

 

  여기서 곰곰이 생각해 봤다. 문제에서 "없애야 하는 전깃줄의 최소 개수" 의 의미를. 

  이 말을 조금 바꿔보면, "[전깃줄의 총 개수 N] - [없앨 필요 없는 전깃줄의 최대 개수]" 임을 알게 됐고, 

[없앨 필요 없는 전깃줄의 최대 개수] = [가장 긴 증가하는 부분 수열의 길이] 임을 알게 됐다!!!!!!!!!!!!!!!!

  

따라서, 주어진 수열(A전봇대 기준으로 오름차순 정렬, B전봇대의 값들을 모아놓은 수열)

[8, 2, 9, 1, 4, 6, 7, 10]

에서의 가장 긴 증가하는 부분수열의 길이를 구하면 된다.

 

가장 긴 증가하는 부분수열의 길이 알고리즘은 다음 문제를 풀면 도움이 된다. 

-> 백준 11053번 : 가장 긴 증가하는 부분수열의 길이 

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

 

<코드>

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

int n;
int dp[101];
int arr[101];
int LISNum = 0;

void LIS(){ //LIS : O(n^2)
    
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 1; j--)
        {
            if (arr[i] > arr[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        LISNum = max(dp[i], LISNum);
    }
    
}
int main(){

    priority_queue <pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    cin >> n;
    for (int i=0; i<n; i++){
        int x, y;
        cin >> x >> y;
        pq.push({x,y});
    }
    int index=0;
    while(!pq.empty()){
        index++;
        arr[index] = pq.top().second;
        pq.pop();
    }

    LIS();

    cout << n - LISNum;
}