[C++]백준 - 2565번 문제

2565번: 전깃줄 (acmicpc.net)

2565번: 전깃줄

 

2565번 : 전깃줄

---

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

< 그림 1 >

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

 

 

출력

---

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

 

 

---

 

생각해 볼 점

---

전깃줄을 없애는 것에 집중하면, 그리디 및 동적계획법으로 푸는 방법을 생각할 수 있지만, 크게 효율적인 방법은 아닐 것으로 짐작됩니다.

 

반대로 생각하는 것이 더 낫습니다. 

 

최대한 적은 전깃줄을 없애는 것이 아니라

 

최대한 많은 전깃줄을 연결하는 쪽으로 생각해봅시다.

 

위의 예제 입력대로 입력을 받았다면, 

이렇게 전봇대가 완성이 될텐데, A 전봇대의 번호 순서대로 B 전봇대에 연결된 번호를 나열해보면

 

{ 8, 2, 9, 1, 4, 6, 7, 10 }의 순서로 나열이 되겠네요.

 

여기서 11053번 문제와 동일한 가장 큰 증가하는 부분 수열을 만들면

 

{ 2, 4, 6, 7, 10 }이 될 것입니다.

 

그러면 이 수열의 길이는 5이며, 이는 최대로 연결할 수 있는 전깃줄 수와 같습니다.

 

실제로 A 전봇대의 번호 순서대로 전깃줄을 연결해 보시면 이것이 정답임을 알 수 있습니다.

 

따라서, 없앨 전깃줄의 갯수는 N - 5 = 3개가 답입니다.

 

결국, 11053번 문제와 동일하게 풀면 되겠습니다.

 

 

코드

---

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

bool sorting(pair<int, int> A, pair<int, int> B)	//A 전봇대 기준으로 숫자를 정렬
{
    return A.first < B.first;
}

int main() 
{
    int N;
    cin >> N;
    
    vector<pair<int, int>> elec;
    int dp[100] = {0, };
    for(int i = 0; i < N; i++)
    {
        int A, B;
        cin >> A >> B;
        
        elec.push_back(make_pair(A, B));
    }
    sort(elec.begin(), elec.end(), sorting);
    
    int result = 100;
    for(int i = 0; i < N; i++)
    {
        int count = 0;
        for(int j = 0; j < i; j++)
        {
            if(elec[j].second < elec[i].second && count < dp[j]) count = dp[j];
        }
        
        dp[i] = ++count;
        count = N - count;
        
        if(count < result) result = count;	//가장 작은 값을 찾음
    }
    
    cout << result;
	return 0;
}

 

그 외

---

저는 이 문제로 4시간을 고민하다가 결국 다른 블로그를 참고하여 풀었습니다.

 

이런 문제를 한번에 어떻게 풀지 알아보는 법은 역시 문제를 많이 해결해보아야 알 수 있는 걸까요?