백준25054 Drone Photo

작성일 | In

문제 링크

  • https://icpc.me/25054

문제 출처

  • 2021-2022 SWERC B번

사용 알고리즘

  • 더블 카운팅

시간복잡도

  • $O(N^2)$

풀이

$O(N^3)$ 풀이는 간단합니다. 행 2개 $i, j$를 고정하면 $A(i,k) < A(j,k)$를 만족하는 $k$의 개수를 구해서 $x\choose2$를 구하면 $O(N^3)$에 해결할 수 있습니다. 그렇다고 자료구조 등을 이용해 이 풀이를 최적화하려고 하면 문제를 풀 수 없습니다. 다른 관점으로 바라보아야 합니다.

$a < b < c < d$인 네 수를 사각형의 꼭짓점으로 잡는다고 합시다. 네 꼭짓점을 배열하는 방법은 24가지이고, $a$을 왼쪽 상단 꼭짓점으로 고정하면 6가지입니다. 6가지 경우를 모두 그림으로 그려봅시다.

1
2
3
a   b  |  a   b  |  a   c  |  a   c  |  a   d  |  a   d
       |         |         |         |         |        
c   d  |  d   c  |  b   d  |  d   b  |  b   c  |  c   b

여기에서 4번째와 6번째는 불가능한 배치입니다. 가능한 배치의 경우, $b$와 $c$는 인접한 두 수 중 하나보다 작고, 다른 하나보다 큽니다. 반대로 불가능한 배치에서는 $b$는 인접한 두 수 모두보다 작고, $c$는 두 수 모두보다 큽니다. 작은 수에서 큰 수로 가는 화살표를 그려보면 더 명확하게 알 수 있습니다.

1
2
3
a → b  |  a → b  |  a → c  |  a → c  |  a → d  |  a → d
↓   ↓  |  ↓   ↓  |  ↓   ↓  |  ↓   ↑  |  ↓   ↑  |  ↓   ↑
c → d  |  d ← c  |  b → d  |  d ← b  |  b → c  |  c ← b

가능한 배치의 경우 각 직사각형은 in-degree와 out-degree가 모두 1인 점을 2개씩 갖고 있으며, 불가능한 배치의 경우 그러한 점이 없습니다. 따라서 더블 카운팅을 이용해 직사각형의 개수를 세는 대신, in-degree = out-degree = 1인 점의 개수를 센 다음 2로 나눠도 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, I[2323232], J[2323232], R[1515], C[1515], A[2323232], B[2323232], X;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) for(int j=1,t; j<=N; j++) cin >> t, I[t] = i, J[t] = j;
    for(int i=1; i<=N*N; i++) A[i] = R[I[i]]++, B[i] = C[J[i]]++;
    for(int i=1; i<=N*N; i++) X += A[i] * (N - B[i] - 1) + B[i] * (N - A[i] - 1);
    cout << X / 2;
}