BOJ 2565 전깃줄

문제 링크 : https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

문제에서 요구하듯이 최적의 방법으로 교차를 제거했다고 가정하자.

교차가 제거되고 남은 것을 생각한다. 문제에서 주어진 그림에서 남겨진 것을 붉은 색으로 표시했다. 

교차하지 않는 남은 선들을 어떻게 기술하면 좋을까? 

붉은 선의 왼쪽 번호의 대소 관계와 오른쪽 선의 대소 관계가 일치한다.

즉, 어느 한쪽을 정렬했을 때, 반대쪽은 증가 수열이다.

생각해보면 교차하지 않는다는 것은 항상 이런 뜻이다.

 

이제 다음의 관계는 이해하기 쉽다.

 

최소로 선을 제거 <==> 최대로 기존 선을 남김 <==> 최장증가 부분수열

 

최장증가 부분수열을 구하는 방법 중에서 여기서는 세그먼트 트리를 사용한다.

세그먼트 트리가 추가적인 조건이 부여된 증가수열을 찾을 때 유연하게 적용될 수 있어서이다.

예를 들어 증가 부분수열에 추가적으로 다음의 조건이 붙어 있다고 하자.

 

이웃하는 항들의 차이가 x 이하여야 한다.

 

크기가 충분히 커서 dp 를 사용할 수 없다면,

나로서는 이런 조건을 수용할 수 있는 방법은 세그먼트 트리 밖에는 모르겠다.

 

세그먼트 트리도 항의 크기와 인덱스 둘 중 어느 것을 기준으로 업데이트 하느냐 선택할 수 있다.

아래 코드는 전자의 방법을 사용한다. 다른 방법들은 다른 글에서 정리한다.

 

#include<bits/stdc++.h>

using namespace std;

pair<int,int> arr[101];
int tree[2000];

void upd(int l,int r,int node,int p,int v){
    if(p<l || r<p) return;
    if(l==r) {
        tree[node]=v;
        return;
    }
    int mid=l+r>>1;
    upd(l,mid,2*node,p,v),upd(mid+1,r,2*node+1,p,v);
    tree[node]=max(tree[2*node], tree[2*node+1]);
}

int qry(int l,int r,int node,int qr){
    if(qr<l) return 0;
    if(r<=qr) return tree[node];
    int mid=l+r>>1;
    return max(qry(l,mid,2*node,qr), qry(mid+1,r,2*node+1,qr));
}

int main(){
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++){
        int a,b; scanf("%d%d",&a,&b);
        arr[i]={a,b};
    }
    sort(arr,arr+n);
    
    for(int i=0;i<n;i++){
        int p=arr[i].second;
        int t=qry(0,500,1,p);   // 500 은 값의 범위이다! (not index)
        upd(0,500,1,p,t+1);
    }
    printf("%d\n",n-tree[1]);
}