[BOJ 34316 // C++] 사각형 개수 세기

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 34316번 문제인 사각형 개수 세기이다.
문제는 아래 링크를 확인하자.

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

 

\(NM\le10^5\) 제약조건을 눈여겨보자. 이 조건으로부터 \(\min(N,M)\le\sqrt{10^5}\)임을 알 수 있다. 이러한 형태로 문제에서 주어지는 입력에 추가적인 제한을 주는 경우는 제법 자주 나타나므로 잘 알아두는 것이 좋다.

 

\(N\)과 \(M\) 중 더 작은 값을 행의 개수로 하고, 두 개의 행을 골라 각 열의 두 행의 수의 합을 각각 구하는 작업의 시간복잡도는 \(O(\min(N,M)^2\max(N,M))=O(\min(N,M)NM)\)과 같다. \(NM\le10^5\)와 \(\min(N,M)\le\sqrt{10^5}\)가 성립하므로, 이와 같은 접근의 연산량은 1초 안에 충분히 수행 가능하는 점을 관찰할 수 있다. 여기까지 관찰했다면 이후의 계산은 어렵지 않을 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

int R, C;
vector<int> v[316];
ll ans;
int cnt[20];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    if (R < C) {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) cin >> v[r].emplace_back();
        }
    }
    else {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                cin >> v[c].emplace_back();
            }
        }
        swap(R, C);
    }

    for (int r1 = 0; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            memset(cnt, 0, sizeof(cnt));
            for (int c = 0; c < C; c++) {
                cnt[v[r1][c] + v[r2][c]]++;
            }
            for (int i = 2; i < 10; i++) ans += cnt[i] * cnt[20 - i];
            int v1 = cnt[10], v2 = v1 - 1;
            if (v1 & 1) v2 /= 2;
            else v1 /= 2;
            ans += v1 * v2;
        }
    }
    cout << ans;
}