[백준]소가 길을 건너간 이유 11(14459)

문제 링크 : [백준]소가 길을 건너간 이유 11(14459)

14459번: 소가 길을 건너간 이유 11

 

문제 설명

왼쪽 길에서 오른쪽 길로 횡단보도를 만들려고 합니다.

그러나 각 왼쪽 지점에서 오른쪽 지점으로 잇기 위해서는 각 지점에 있는 숫자의 차이가 4이하여야 횡단보도를 지을 수 있습니다.

또한 횡단보도가 서로 엇갈리지 않도록 지어야합니다.

이때 최대한 많이 만들 수 있는 횡단보도의 갯수를 구하세요.

입력

N(지점의 갯수, 1 <= N <= 100,000)

A_i(왼쪽 지점 별 숫자, 1 <= A_i <= N)

B_i(오른쪽 지점 별 숫자, 1 <= B_i <= N)

6
1
2
3
4
5
6
6
5
4
3
2
1

 

출력

5

 

카테고리

#정렬 #LIS

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. 왼쪽에서 오른쪽으로 엇갈리지 않도록 잇는 문제입니다.
2. 엇갈리지 않고 최대한 매핑하는 문제는 LIS로 풀 수 있습니다.
   1. 한쪽(왼쪽)을 기준으로 정렬을 합니다.
   2. 다른쪽(오른쪽) 값들 중 임의의 두 값(A, B)이 내림차순이라면 두 지점을 잇는 선을 서로 교차하게 됩니다.
   3. 이때 교차하지 않게 최대한 많은 쌍을 구한다는 것은 오름차순으로 이루어진 최장 부분수열을 구하는 것과 같습니다.
   4. 즉 LIS를 구하는 문제가 됩니다.
3. 그러나 이 문제는 단순히 왼쪽 값과 오른쪽 값을 서로 매핑하는 것이 아니고, 두 수의 차이가 4이하인 곳을 모두 이을 수 있습니다.
4. 그렇다면 모든 쌍들 중에 차이가 4이하인 것들을 모두 만들어서 LIS를 구하면 됩니다.
5. LIS를 O(NlogN)에 구할 수 있고, 이때 N은 실제로 N*9가 됩니다.(차이가 4이하인 곳들과 이을 수 있기 때문에 왼쪽 지점을 기준으로 최대 9개의 횡단보도를 만들 수 있습니다.)
6. LIS를 돌리는 것은 문제가 없으나, 차이가 4이하인 지점들을 찾는데 무식하게 풀면 O(N²)의 시간복잡도가 걸립니다.
7. 따라서 빠르게 쌍을 찾아야합니다.
8. 왼쪽 값을 따로 저장한 후, 오른쪽 값을 저장할 때 그때의 인덱스와 함께 저장합니다.
9. 오른쪽을 값으로 정렬합니다.
10. 왼쪽 값을 저장한 배열을 순서대로 돌면서, 그 때의 값을 기준으로 오른쪽 배열에서 -4 ~ +4 까지의 인덱스와 매핑 정보를 만듭니다.
    1. 왼쪽 값이 5라면 오른쪽 지점 중, 1~9까지의 숫자와 매핑을 할 수 있고, 그때 값들을 가지고 미리 정렬을 했기 때문에, 왼쪽 값을 기준으로 쉽게 찾을 수 있습니다.
11. 모든 매핑정보가 완성되면 LIS를 구합니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#include<vector>
#include<algorithm>
#define N 100001
using namespace std;
typedef pair<int,int>P;
int n,d[N],i,j,x;
P p[N];
vector<P>v;
vector<int>w;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)cin>>d[i];
    for(i=1;i<=n;i++)cin>>p[i].first,p[i].second=i;
    sort(p+1,p+1+n);
    for(i=1;i<=n;i++)for(x=d[i],j=max(1,x-4);j<=min(n,x+4);j++)v.push_back({i,-p[j].second});
    sort(v.begin(),v.end());
    for(P x:v){
        if(w.empty()||w.back()<-x.second)w.push_back(-x.second);
        else *lower_bound(w.begin(),w.end(),-x.second)=-x.second;
    }
    cout<<w.size();
}