[백준] 북서풍(5419)

문제 링크 : [백준] 북서풍(5419)

문제 설명

n개의 섬의 x, y좌표가 주어졌을 때, 동남쪽(X좌표 증가, Y좌표 감소)으로 이동하여 이동 할 수 있는 섬의 쌍의 갯수를 구하세요.

입력

T(테스트 케이스 수, 1<=T<=100)
N(섬의 갯수, 1<=N<=75,000)
X_i Y_i(섬의 x,y 좌표, -10⁹<=X<_i, Y_i<=10⁹)

2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1

출력

각 테스트 케이스 별로 가능한 쌍의 갯수를 출력합니다.

5
3

카테고리

#펜윅트리, #세그먼트트리, #라인스위핑

시간 복잡도 상한

O(NlogN)까지 가능합니다.

해결 방법

1. 한 섬을 기준으로, Y가 작으면서, X가 큰 섬의 갯수를 구하면 됩니다.
2. 모든 섬을 한 축을 기준으로 정렬합니다.(코드상에서는 x축을 기준으로 오름차순)
3. x좌표로 정렬이 되어 있기 때문에, 현재 섬보다 먼저 나왔다면, x좌표는 현재 섬보다 작거나 같다는 것이 보장됩니다.
4. y축만 현재 섬의 y좌표보다 큰 것의 갯수를 세면됩니다.
5. 이런 모양의 문제들(현재 위치에서 조회하고자 하는 범위의 부분합을 조회하고, 현재 데이터의 상태를 업데이트 해주는 문제)은 세그먼트 트리의 형태로 풀면됩니다.
6. 단, 여기서는 두가지 이유 때문에, y축의 부호를 반대로 하여 데이터를 저장합니다.
   6-1. 데이터를 x축 오름차순, y는 내림차순으로 졍렬해야합니다.(기본은 오름차순)
   6-2. 나중에 조회할 때도, 특정 값보다 큰 값을 조회하기 위해서는 펜윅트리로 구현한 경우, 두번을 조회해야합니다.(최대값까지의 누적합 - 현재 값보다 작은 누적합)
7. 풀이 로직은 여기까지이나, 중요한 한가지 문제가 있습니다.
   7-1. x 좌표의 값은 대소비교만을 위하여 쓰이므로, 자료형 범위 안에만 들어오면 아무런 문제가 없습니다.
   7-2. 하지만 y좌표는 세그먼트 트리에서 인덱스로 참조해야 하기 때문에 10
   ⁹의 범위는 세그먼트 트리에 담기에는 너무 큰 범위입니다.
   7-3. 곰곰히 생각해보면 y좌표 또한 대소비교만 하면 되는 것이지 실제 값이 필요하지는 않습니다.
   7-4. n이 최대 75,000이므로 실제 하나의 테스트케이스에 나타날 수 있는 y좌표의 갯수는 많아야 75,000가지 입니다.(비둘기집 원리)
   7-5. 따라서 실제 y좌표의 값을 대소관계만 나타날 수 있는 수로 변경합니다.
   7-6. 코드에서는 map을 통하여 했습니다. (주의해야 될 사항은, C++의 경우 map이 tree map으로 키가 정렬된 상태로 iterator를 반환해주어, 순서대로 처리하면 되지만 java에서 HashMap을 쓸 경우에는 순서가 보장되지 않습니다.)

시간복잡도

O(NlogN)

코드

#include<iostream>
#include<map>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>p;
int t,n,i,x,y;
long long f[75001],s;
vector<p>v;
map<int,int>z;
void init(){
    v.clear();
    z.clear();
    memset(f,0,sizeof(f));
    s=0;
}
void u(int p){
    while(p<=n)f[p]++,p+=p&-p;
}
long long q(int p){
    long long s=0;
    while(p)s+=f[p],p-=p&-p;
    return s;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        init();
        cin>>n;
        for(i=0;i<n;i++){
            cin>>x>>y;
            v.push_back({x,-y});
            z.insert({-y,0});
        }
        i=1;
        for(p k:z)z[k.first]=i++;
        for(i=0;i<n;i++)v[i].second=z[v[i].second];
        sort(v.begin(),v.end());
        for(i=0;i<n;i++)s+=q(v[i].second),u(v[i].second);
        cout<<s<<"\n";
    }
}