[BOJ 2568]전깃줄-2

[BOJ 2568]전깃줄-2

알고리즘 분류상으로 LIS로 되어있기 때문에 어렵지 않게 풀기는 했다만, 만약 분류를 모른 상태로 접했다면 어떻게 풀어야 할지 고생했을 문제이다. 이런 부류의 문제를 풀 때는 어떻게 LIS로 푸느냐 보다는, 왜 이 문제가 LIS로 풀릴 수 있는지를 파악하는 것이 더 중요하다. 전깃줄1 문제도 있는데, 없애야 할 전선의 최소 개수를 구하는 것은 같지만 2는 거기서 구체적으로 몇 번째의 전선을 없애야 하는지를 더 구해야한다. 게다가 N이 최대 10만으로 늘어났기 때문에 LIS를 구하는 알고리즘도 O(NlogN)만에 구해야 한다. 사실 구하는 법을 까먹어서 예전 소스를 슬쩍 보고왔다.

우선 왜 이 문제가 LIS에 해당하는지부터 알아보자. 이 문제에서 핵심은 전선끼리 교차하는 경우가 있어서는 안된다는 것이다. 그렇다면 언제 교차할 수 밖에 없는 상황이 생기는가? 예시 데이터로 생각해보자.

위 경우는 전선끼리 교차하는 경우가 없는 케이스이다.

하지만 이 케이스에서는 교차가 발생한다. 그렇다면 첫 번째와 두 번째 케이스 사이의 차이는 무엇일까? 바로 왼쪽 4번이 (오른쪽과)연결된 번호의 차이이다. (교차가 없었던)첫 번째 케이스에서는 왼쪽 번호가 1->2->3->4로 커져갈수록 그와 연결된 오른쪽도 동시에 2->3->4->5로 증가했다. 하지만 (교차가 발생한)두 번째 케이스에서는 왼쪽 번호가 1->2->3->4로 커져갔지만 오른쪽은 2->3->4->1로 값이 증가 관계가 한번 어긋났다. 이것이 바로 교차를 만든 이유이다. 그래서 정리하자면 교차의 원인은 이렇게 설명할 수 있다. 왼쪽 번호를 오름차순으로 정렬을 한 상태에서 오른쪽 번호를 살펴볼 때, 일관되게 증가하지 않으면 반드시 교차가 생기게 된다. 이 문제에서는 교차하는 전선이 발생하지 않게끔 최소한의 전선을 제거해야 하므로, LIS를 찾은 다음 그 LIS에 포함되지 않는 번호를 삭제하면 된다. 그럼 이제 문제는 LIS를 O(NlogN)만에 구하는 것이다. 지금까지 나온 수 중에서 현재 수보다 작은 수의 개수를 세야하는데 그 방법은 lower bound를 사용하면 된다.

맨 처음에는 아무 것도 없는 상태이다. 여기서 idx값은 현재 내가 저장하고 있는 dp배열 안에 있는 원소의 수이다.

첫 번째 원소로 8이 들어왔다. 그 이전에는 아무 것도 없었으므로 그냥 넣어주면 되고, idx를 1 증가시킨다.

그 다음 2가 들어온다. 여기서부터 lower bound를 찾는다. 그 결과 2는 8의 자리를 대체하게 된다.(idx는 그대로)

그 다음 9가 들어온다. 9는 현재 dp 배열에 저장된 값 중에서 가장 큰 값인 2보다도 크므로 idx를 1 증가시킴과 동시에 dp배열에 추가한다.

다음 1이 들어온다. lower bound 결과 2를 밀어내고 1이 대체한다.

그 다음 4는 9를 밀어낸다.

그 다음 6은 4뒤에 추가된다.

역시 6뒤에 7이 추가된다.

마지막으로 10이 추가되어서 최종 1 4 6 7 10이 된다.

위 결과만 보면 dp배열에 저장되는 값이 곧 LIS의 구성 원소라고 생각할 수 있겠으나 사실 이는 우연의 일치이다. 예를 들어 2 3 1이라는 데이터로만 돌려봐도 실제 dp배열에는 (2,3)이 아닌, (1,3)이 저장된다. 즉 dp배열은 idx를 통해서 LIS의 길이만 알아낼 수 있지, 구성 원소까지 일치한다고 확신할 수는 없다. 하지만 문제에서는 실제 구성원소를 알아야 삭제해야 할 원소를 알아낼 수 있기 때문에 결국 우리는 구성원소까지 구해야 한다. 구성원소를 추적하는 과정은 그리 어렵지 않다. 나는 idx_arr[]라는 별도의 배열을 만들어서 for문의 매 루프마다 idx값을 idx_arr[]배열에 저장한 다음, ans(최종 LIS의 길이)값을 갖고 끝에서부터 보면서 idx_arr[]값과 같으면 그 값이 구성원소라고 생각했다. 이 과정에서 나는 이전 값과 현재 값의 대소 비교 없이 그냥 (ans==idx_arr[])만 만족하면 되는지 의심이 들었는데, 결론은 그래도 문제 없다. 만약 대소 비교과정에서 문제가 생길 수 있다면, 그 값의 idx_arr[]는 ans가 이미 아니기 때문이다. 거꾸로 (idx_arr[]==ans) 라는 것은 반드시 이전 값보다 작다는 확신이 있다는 뜻이다.

#include<stdio.h>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 100009
typedef pair<int,int> pii;
pii arr[SIZE];
int dp[SIZE]={0},idx_arr[SIZE];
int main(){
    int n;  scanf("%d",&n);
 
    for(int i=0 ; i< n ; i++){
        scanf("%d %d",&arr[i].first,&arr[i].second);
    }
 
    sort(arr,arr+n);
 
    int idx=0,start=-1,ans=0;
 
    for(int i=0 ; i<n ; i++){
        int cur=arr[i].second;
 
        int l=0,r=idx,mid,tmp=0;
 
        if(cur>dp[idx]){
            dp[++idx]=cur;
            idx_arr[i]=idx;
        }
        else{ 
            while(r>=l){
                mid=(l+r)/2;
 
                if(dp[mid]>cur){
                    r=mid-1;
                    tmp=mid;
                }
                else l=mid+1;
            }
            dp[tmp]=cur;
            idx_arr[i]=tmp;
        }
 
        if(ans<idx_arr[i]){
            ans=idx_arr[i];
            start=i;
        }
    }
    printf("%d\n",n-ans);
 
    vector<int> v;
    for(int i=n-1 ; i>=0 ; i--){
        if(ans==idx_arr[i]){
            ans--;
        }
 
        else {
            v.push_back(arr[i].first);
        }
    }
 
    reverse(v.begin(),v.end());
    for(int here:v)
     printf("%d ",here);
 
 
    return 0;
}