BAEKJOON 1615번: 교차개수세기

https://www.acmicpc.net/problem/1615

1615번: 교차개수세기

들어가며..

기존에 이 문제의 풀이는 \(O(M \log(N)) \)에 작동하는 세그먼트 트리를 활용하는 것으로 알려져 있었다. 하지만, 이번 포스팅에서는 조금 다른 풀이를 다루고자 한다.

 

풀이

무려 \(O(NM)\)에 작동하는 코드가 통과된다.

먼저, 간선이 연결된 정점 중, A에 속한 정점을 기준으로 단조 증가하게 정렬한다. (만약 그 정점이 같은 것 들은 B에 속한 정점을 기준으로 단조 증가하게 정렬한다) 그 후, 모든 간선을 확인해 주면서, 정렬 순서에서 앞에 있는 간선들 중 지금 확인하는 간선 보다 B에 연결된 정점의 번호가 큰 것들의 개수를 세어주면 된다. 이 해법은 세그먼트 트리를 활용하는 풀이에서, 세그먼트 트리를 통해 합을 구하는 부분을 Naive하게 해주는 방식이다.

 

\(O(NM)\)이 통과되는 이유

\(M \in [1, \frac{N(N-1)}{2}]\)이기 때문에 상식적으로 생각해서는 \(O(NM)\)에 작동하는 코드가 통과되어서는 안된다.

 

우리가 이 해법으로 문제를 해결할 수 있는 이유를 알아보기 위해서, 먼저, 문제에 적힌 조건을 보아야 한다.

문제의 입력 조건에는 다음과 같은 문장이 있다. "중복되는 간선이 주어지지 않는다." 이 조건을 통해서 우리의 코드가 총 몇 번의 연산을 하게 되는지 예상할 수 있다.

 

간선의 개수가 가장 많을 때, 즉, \(M=\frac{N(N-1)}{2}\)일 때를 생각해 보자. 본문에서 이용하는 풀이를 저격하기 위해서, 간선이 연결된 정점 중 B에 연결된 정점의 번호는 최대한 작게 만들어야 한다. 따라서, A에 속한 모든 \(N\)개의 정점과 B에 속한 정점 중 \(1\) ~ \(\frac{N-1}{2}\)의 번호를 가진 정점에 각각 연결된 간선을 가진다. 다만, \(N\)이 짝수일 때는 간선의 수 보다 더 크게 잡아서 \(1\) ~ \(\frac{N}{2}\)의 번호를 가진 정점에 연결되어 있다고 하자.

 

간선 \(e_i\)에 연결된 정점 중 A 속한 것을 \(a_i\), B에 속한 것을 \(b_i\)라 하자.

그러면, 코드의 for문에서는 간선 \(e_i\)에 대해 \(b_{i}-a_{i}\)번의 연산을 하게 된다. 이는 \(a_i\)가 같은 간선들로 묶어서 생각하면, \(a_i\)마다, \(\sum_{k=1}^{\frac{N}{2}}k\) 번의 연산을 하게 됨을 알 수 있다. 그렇다면 이 문제를 해결하는 데에 이용되는 연산은 \(\frac{(\frac{N}{2}-1)(\frac{N}{2})(N)}{2} + \alpha\)회 보다 작거나 같다.

 

이때, \(f(N)=\frac{(\frac{N}{2}-1)(\frac{N}{2})(N)}{2} + \alpha\)라 하면, \(f(N) \in O(\frac{N^3}{8})\)이며, \(\frac{N^3}{8} \le 10^9\)이다. 그리고 간단한 덧셈만을 수행하고 있으므로, 충분히 제한 시간안에 AC를 받을 수 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
pair<ll,ll>A[4000003];
ll cnt[2003];
int main(){
    ios_base::sync_with_stdio(false);
    int N,M;cin>>N>>M;
    for(int i=1;i<=M;i++)cin>>A[i].first>>A[i].second;
    sort(A+1,A+1+M);
    ll ans=0;
    for(int i=1;i<=M;i++){
        ll now=0;
        for(int j=A[i].second+1;j<=N;j++)now+=cnt[j];
        cnt[A[i].second]++;
        ans+=now;
    }
    cout<<ans;
    return 0;
}