[백준 알고리즘] 2565번 : 전깃줄(C++)

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

문제

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

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

![](https://www.acmicpc.net/upload/assets/post_images/i7Wn4h3qIiezi.jpg” />

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

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

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

풀이+잡생각

문제를 풀면 풀수록 문제를 해결하는 것 보다, 효율적으로 해결하는게 중요하다는 것을 점점 느낀다. 오늘 푼 문제는 LIS(최장 부분 수열)로 해결하는 문제였다. LIS를 이전에 접했었는데, 머릿속에 남아있지 않아서 다시 정리하고 문제를 풀었다. LIS에 대한 내용은 포스팅으로 정리해야겠다.

이전에 풀었던 LIS는 아주 기초적이고 직관적인 문제였는데, 이번 문제는 LIS를 사용해야한다는 것을 알면서도 어떻게 해야할지 감이 안잡혔다. 혼자 한시간 가까이 끙끙대다가 문득, ‘왜 입력예시는 정렬이 된 채로 안들어갈까?’ 라는 의문이 들었다. 입력 예시가 1, 8 > 3, 9 > 2, 2 이런식으로 무작위로 들어간다. 그래서 짝으로 들어가는 입력 A, B 중 A를 기준으로 정렬을 시켜보았다. 그랬더니 B를 보았을 때, 지워야하는 전선들이 최장 수열을 방해하고 있다는 것을 알게되었다.

입력과 출력 예시를 통해서 발견해서 사실 좀 찝찝하긴 하다. LIS를 사용해야한다는 것도 알고 있었고.. 좋은 조건 속에서도 해결 방향을 빨리 잡아내지 못하는게 아쉽기도 하다..

문제는 DP로 해결했다. 사용한 자료구조는 set, vector, pair 이다. 일단 입력을 받고 A를 기준으로 오름차순으로 정렬을 해줘야하는데, 나중에 한번에 하면 시간이 복잡도가 증가될 것 같아서 어차피 중복되는 전깃줄 숫자가 없다고 했으니, set에 넣기로 하였다. 그리고 A, B를 쌍으로 넣어야하기에 pair 컨테이너에 하나로 묶어서 집어넣었다. vector가 아니기 때문에 인덱싱으로 접근할 수 없고 iterator를 사용해야 하는데, 나중에 dp를 수행할 때 헷갈릴 것 같아서 별도의 벡터에 B 전봇대의 수열만 따로 담아두기로 하였다.

DP는 이분탐색을 이용한 LIS를 수행하는게 가장 좋겠지만 아직 이분탐색을 사용하는 방법에 대해서 잘 몰라서 일단 알고 있는 n^2 로 해결하는 방법을 택했다. DP라고는 하지만 사실상 완전탐색이나 다름없다. 알고리즘은 단순하게 모든 수열을 다 돌면서 자기보다 낮은 인덱스에 있는 수들을 비교해 현재위치의 최장 수열 길이를 구하는 방식이다. 가장 긴 길이가 구해지면, 전체 B의 벡터길이에서 lis 길이를 뺴주어 없애야 하는 전깃줄의 숫자를 구했다.

사실 처음 제출했을 때 틀렸습니다가 나와서 좀 당황했는데, 알고보니 내가 바보처럼 dp안에 들어있는 최장 길이를 안찾고 아무생각없이 가장 마지막 유효한 인덱스에 있는 값을 구했다.

학기 중에 쉽지 않겠지만 열심히 풀자!

코드

#include<iostream>
#include<vector>
#include<set>
#include<algorithm> // max 함수를 쓰기 위해

using namespace std;

int dp [101] = {0}; // dp를 위한 배열. 전깃줄의 최대 갯수는 100개이다.

int main(){
    int T;
    cin >> T;
    set<pair<int, int>> bot; // pair로 받는다. set 자료구조에 넣기 때문에 first를 기준으로 정렬된다.
    while(T--){
        int a, b;
        cin >> a >> b;
        bot.insert(make_pair(a, b)); // set에 insert하기
    }

    vector<int> b;
    for (auto it = bot.begin() ; it != bot.end() ; it++){
        b.push_back(it->second); // 이 작업은 사실 안해도 되긴 하는데, lis계산을 편하게 하기 위해서 만들었다. second만 모아서 새 벡터에 저장.
    }

    // LIS를 구하는 식. O(n^2)이다.
    for (int i = 0 ; i < b.size() ; i++){
        if (dp[i] == 0) dp[i] = 1;
        for (int j = 0 ; j < i ; j++){
            if(b[i] > b[j] && dp[j]+1 > dp[i]){
                dp[i] = dp[j]+1;
            }
        }
    }

    // 부분 수열 중 가장 길이가 긴 녀석을 찾자.
    int lis = 0;
    for(int i = 0 ; i < b.size() ; i++){
        lis = max(lis, dp[i]);
    }

    // 전체 크기에서 빼주면 없애야할 전깃줄의 갯수가 나온다.
    cout << b.size() - lis;
    return 0;
}