[BOJ] 7453 - 합이 0인 네 정수

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

BOJ - 합이 0인 네 정수

문제 유형: 이진탐색, 해시, 투포인터, MITM(Meet-In-The-Middle)

문제 난이도: Gold II

시간 제한: 12초

메모리 제한: 1024MB

 

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2^28이다.

 

출력

합이 0이 되는 쌍의 개수를 출력한다.

 

풀이

브루트 포스는 n^4의 시간복잡도를 갖는다.

MITM을 이용하면 훨씬 빠르다.

 

두 배열씩 짝을 지어서 가능한 모든 조합을 만든다. 그뒤 다른 두 배열의 조합에서 합해서 0이 되어줄 상대방 조합의 개수를 구하면 된다.

만약 해시맵으로 구현하고 싶다면 mp[c[i]+d[j]]++를 해서 개수를 누적해주면 된다.

이진탐색으로는 다른 배열에 대해 upper_bound한 위치에서 lower_bound한 위치를 빼주면 된다.

 

해시맵 구현에서의 주의할점은, 너무 많은 값들을 쓰므로 TLE가 나올 수 있다. 그러므로 reserve를 이용해서, n*n의 넉넉한 크기를 마련할 필요가 있다.

 

이진탐색에서의 주의할점은, 이진탐색의 대상 배열뿐만 아니라 두 조합 배열 모두를 정렬하는 것이 빠르다는 것이다.

이는 캐시 적중률 때문이다. 순차적인 값들간에 지역성이 클수록 아무래도 반복되는 작업에서 더 빠르다.

 

자료형의 크기에 유의하자. 정답은 32 부호있는정수를 넘는 값이 될 수 있다.

 

코드

C++

 

이진탐색 풀이

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n), d(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }

  vector<ll> ab, cd;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      ab.emplace_back(a[i] + b[j]);
      cd.emplace_back(c[i] + d[j]);
    }
  }

  ll ans = 0;

  int m = ab.size();
  sort(ab.begin(), ab.end());
  sort(cd.begin(), cd.end());

  for (int i = 0; i < m; ++i) {
    ll target = -ab[i];
    int l = lower_bound(cd.begin(), cd.end(), target) - cd.begin();
    int r = upper_bound(cd.begin(), cd.end(), target) - cd.begin();

    ans += r - l;
  }

  cout << ans << "\n";

  return 0;
}

 

 

해시를 이용한 풀이

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;
  vector<int> a(n);
  vector<vector<int>> groups(3, vector<int>(n));

  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> groups[0][i] >> groups[1][i] >> groups[2][i];
  }

  unordered_map<ll, ll> mp;
  mp.reserve(n*n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      mp[groups[1][i] + groups[2][j]]++;
    }
  }

  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    ll target = -a[i];
    for (int j = 0; j < n; ++j) {
      ll required = target - groups[0][j];
      if (mp.find(required) != mp.end())
        ans += mp[required];
    }
  }

  cout << ans << "\n";

  return 0;
}