소가 길을 건너간 이유 11

boj 14459

 

아무리 생각해도 dp로 푸는 시간 복잡도 $O(N^2)$, 공간복잡도도 $N^2$ 인 풀이밖에 생각이 나지 않았다.

따라서 답지를 봤는데... 자바 언어로 되어 있어서 해석하기 힘들었다. 그리고 처음에 lattice point를 어떻게 잡는다는 것인지도 헷갈렸다. 꽤 오랜 시간을 쓰고 나서 이해했고 직관적인 꽤 간단한 풀이가 있음을 알 수 있었다.

 

먼저 목초지가 왼쪽과 오른쪽으로 나눠져 있다.

밑의 코드를 참고하면 쉽게 이해할 수 있을테지만 문자 정의부터 내리겠다.

$a[i]$ : 왼쪽 목초지의 $i$번째 종류

$s[i]$ : 오른쪽 목초지에서 종류 $i$ 목초지의 위치

(단, $index$는 $0$부터 $n-1$이다.)

 

그리고 dp와 segment tree를 이용할 것이다.

구간 $[l,r]$의 최댓값을 반환하는 segment인데...

이때 구간 $[l,r]$의 최댓값이란 왼쪽 목초지의 $l$번째 목초지부터 $r$번째 목초지를 오른쪽 목초지와 연결을 할 것인데(물론, 사이가 좋은 목초지끼리) 그 때 만들수 있는 최대 횡단보도의 개수이다.

즉, 정답은 segment tree에서 구간 $[0,n-1]$의 최댓값을 반환하면 될 것이다.

 

이제 update과정을 알아볼 것이다.

왼쪽 목초지의 앞에서부터 차례대로 진행하는데 $i$번째 목초지의 update과정을 살펴보자.

$i$번째 목초지는 종류가 $a[i]$일 것이다. $a[i]-4 \sim a[i]+4$까지가 친구이므로 vector에 $s[a[i]-4] \sim s[a[i]+4]$ 의 순서를 저장해놓고 정렬하여 감소하는 순으로 update할 것이다. (왜 감소하는 순서인지는 바로 뒤에 설명하겠다)

 

각 vector의 원소를 $v[k]$라 하면,

$v[k]$ 위치의 값을 구간 $[0,v[k]-1]$의 최대 횡단보도개수에 $1$을 더한 것으로 update해주면 된다.

원소 값(index)이 높은 순으로 update가 진행되기 때문에 $index i$ 가 고정된 상황에서 각각의 update는 다른 update에 영향을 안준다.

 

더 자세한 내용은 코드로..

int n;
int sz(1);
int a[100000];
int s[100000]; //오른쪽 길의 목장의 i 소의 목초지가 몇번째에 있는가
int seg[400000];
 
void update(int pos,int val){
    pos+=sz;
    seg[pos]=val;
    for(pos/=2;pos>0;pos/=2)
        seg[pos]=max(seg[pos*2],seg[pos*2+1]);
}
 
int query(int l,int r){
    l+=sz;
    r+=sz;
    int ret=0;
    while(l<=r){
        if(l%2==1) ret=max(ret,seg[l++]);
        if(r%2==0) ret=max(ret,seg[r--]);
        l/=2; r/=2;
    }
    return ret;
}
 
int main(){
    cin>>n;
    while(sz<n) sz*=2;
    for(int i=0;i<n;i++){
        scanf("%d",a+i);
        a[i]--;
    }
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        x--;
        s[x]=i;
    }
    //왼쪽 길의 i번째 목초지의 친한 소들 부터 오른쪽으로 매칭
    //이 떄 segment tree를 이용할텐데 구간 [l,r]의 segment tree의 반환값은
    //그 구간내에서 매칭할 수 있는 최대 횡단보도 수이다.
    for(int i=0;i<n;i++){
        vector<int> f;
        f.clear();
        //j는 a[i]의 친구
        for(int j=max(0,a[i]-4);j<=min(n-1,a[i]+4);j++){
            f.push_back(s[j]);
        }
        sort(f.begin(),f.end());
        //i의 친구중에 높은 index에 있는 친구부터 구간 update
        int len=f.size();
        for(int k=len-1;k>=0;k--){
            //m값은 구간 [0,v[k]-1] 의 최대 횡단보도 개수
            int m=query(0,f[k]-1);
            //f[k]값을 m+1으로 수정해야 한다.
            update(f[k],m+1);
        }
    }
    cout<<query(0,n-1);
    return 0;
}

이제 소가 길을 건너간 이유 12만 남았다...그런데 해설을 아직도 이해 못하겠다ㅠㅠ