[ 백준 2565 ] 전깃줄 (C++)

백준의 전깃줄(2565) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

전깃줄끼리 서로 교차하지 않게 만들기 위해서 없애야 하는 전깃줄의 최소 갯수를 구해야 하는 문제이다.

먼저, 입력 부분을 살펴보게 되면, 순서가 뒤죽박죽으로 주어진다.

즉, 전봇대를 왼쪽 전봇대들과 오른쪽 전봇대들로 나눠서 생각했을 때, 왼쪽 전봇대들이 1번부터 N번까지 순차적으로 주어지는 것이 아니라, 무작위로 주어진다는 것이다.

그래서 본인은 먼저 왼쪽 전봇대들을 1번 ~ N번 순서대로 맞춰질 수 있도록 정렬을 시켜 주었다.

정렬을 시킨 후에는 더 이상 전봇대들이 꼬이지 않도록 만들어 주어야 한다.

그럼 다음과 같은 예를 생각해보자.

.

정렬을 시켰더니 위와 같은 결과가 나왔다고 가정해보자.

전깃줄이 꼬이지 않도록 만들기 위해서, 없애야 하는 전깃줄의 최소 갯수는 몇 개일까 ?

눈으로 봐도 알겠지만 1개이다. 바로 1번과 6번을 연결시켜놓은 전깃줄을 없애버리면 된다.

그럼, 없앴다고 가정을 해보자. 없앴다고 가정을 한 후에, "전깃줄이 연결되어 있는 오른쪽 전봇대들의 번호" 를 한번 살펴보자.

바로, [ 1 , 2 , 3 , 4 , 5 ] 가 된다. 마치, 오름차순으로 정렬되어 있는 형태라는 것을 알 수 있다.

즉 ! 우리는, 없애야 하는 전깃줄의 최소 갯수를 구해야 하는데, 이는 반대로 생각해보면, 연결할 수 있는 가장 많은 전깃줄의 갯수를 구하더라도 이를 통해서 정답을 도출해 낼 수가 있다.

왜냐하면, 없애야 하는 전깃줄의 최소 갯수는 N - 없앨 필요가 없는 전깃줄의 최대 갯수 와 동일하기 때문이다.

없애지 않아도 되는 전깃줄의 최대갯수는 오른쪽 전봇대에서 "가장 긴 증가하는 부분수열"을 구하는 과정과 동일하다.

위의 그림을 다시 한번 이야기해보자.

오른쪽 전봇대들의 연결된 순서대로 번호를 적어보면, [ 6 , 1 , 2 , 3 , 4 , 5 ] 가 된다.

우리는 이 중에서, 가장 긴 증가하는 부분수열은 [ 1 , 2 , 3 , 4 , 5 ] 라는 것을 알 수 있다.

정리해보면...

1. 왼쪽 전봇대를 기준으로 정렬을 시켜준다.

2. 오른쪽 전봇대에서 "가장 긴 증가하는 부분 수열"을 구해준다.

3. 2번과정에서 구한 "가장 긴 증가하는 부분 수열"의 크기를 N에서 빼준다.

위와 같이 계산을 진행한다면, 답을 도출해 낼 수 있따.

그럼, "가장 긴 증가하는 부분 수열" 에 대해서 알아볼 것인데, 이 부분에 대한 구체적인 내용은 아래의 링크를 참고하길 바란다.

아래의 링크는 백준의 가장 긴 증가하는 부분 수열(11053) 문제에 대한 풀이인데, 이 문제의 풀이와 동일한 방법으로 구할 수 있기 때문에, 링크를 걸어놓도록 하겠다.

[ 가장 긴 증가하는 부분수열 구하는 방법 (Click) - 백준 가장 긴 증가하는 부분수열(11053) ]

[ 소스코드 ]

#include <iostream>
#include <algorithm>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
struct LINE
{
    int Left;
    int Right;
};
 
int N;
int DP[MAX];
LINE Line[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Line[i].Left >> Line[i].Right;
    }
}
 
bool Cmp(LINE A, LINE B)
{
    if (A.Left < B.Left) return true;
    return false;
}
 
void Solution()
{
    int Correct_Line = 0;
    sort(Line + 1, Line + N + 1, Cmp);
    for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (Line[i].Right > Line[j].Right)
            {
                DP[i] = Max(DP[i], DP[j] + 1);
            }
        }
        Correct_Line = Max(Correct_Line, DP[i]);
    }
    cout << N - Correct_Line << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}