[백준/C++] 2565번 전깃줄

문제

 

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

---

Algorithm

전깃줄이 교차하지 않기 위해서는 어떤 형태로 배치되어야 하는지 파악하는 것이 핵심이다.
"연결되어 있는 B의 번호들이 오름차순을 이룬다면, 전깃줄은 교차하지 않는다."

위 아이디어만 파악했다면, 다음 과정을 차례대로 수행한다.

1. 문제에서의 그림과 같은 형태로 전깃줄을 배치하기 위해, A 전봇대의 번호를 기준으로 오름차순 정렬한다.
2. 이제 B에 연결된 전깃줄들이 오름차순을 이루어야 하므로, 가장 긴 증가하는 부분 수열의 길이를 구한다.

       여기서, 가장 긴 증가하는 부분 수열의 길이를 구하는 과정은 다음과 같다.
       1. 이전 지점보다 현재 지점의 값이 크다면, 현재 지점까지의 증가하는 부분 수열의 길이가 1 증가한다.
       2. 현재 지점에서의 모든 이전 지점을 순회하며, 증가하는 부분 수열의 길이가 가장 긴 값으로 현재 지점을 갱신한다.
       3. 모든 지점을 순회하며 갱신되는 값 중 최댓값이 가장 긴 증가하는 부분 수열의 길이가 된다.

3. 출력할 답안은 없애야 하는 전깃줄의 개수이므로, (전체 전깃줄의 갯수 - 가장 긴 증가하는 부분 수열의 길이)를 출력한다.

 

---

 

 

Code

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

int n;
vector<pair<int,int>> wire;
int dp[101];

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int a,b; cin >> a >> b;
        wire.push_back({a,b});
    }
}


void SOLVE()
{
    sort(wire.begin(),wire.end());
    dp[0] = 1;

    int longest = 1;
    for(int i = 1; i < n; i++)
    {
        int temp = 1;
        for(int j = 0; j < i; j++)
        {
            if(wire[j].second < wire[i].second)
            {
                temp = max(temp, dp[j] + 1);
            }
        }
        dp[i] = temp;
        longest = max(longest,dp[i]);
    }

    cout << n - longest;

}

int main()
{
    INPUT();
    SOLVE();
}