[백준] Facebook - 20501

문제 링크

20501번: Facebook

 

문제에서 요구되는 과정은 아래와 같습니다.

1. 각 쿼리별 공통된 요소 검색
2. 검색 결과로 나온 공통된 요소 개수 계산

비교를 요하는 쿼리수가 최대 500,000이므로 각각의 과정이 200 미만의 계산 횟수를 가져야 합니다.

 

쿼리별 공통 요소 검색

bit 연산을 활용한다면 O(1) 시간 안에 공통된 요소를 찾을 수 있습니다.

하지만 비교 대상의 수만큼 메모리를 사용하므로 연산 가능한 범위만큼 값이 주어지는지 확인해야 합니다.

 

이번 문제에서 필요한 최대 비트 수는 2000비트로 충분히 연산 가능한 범위입니다.

 

검색 결과로 나온 공통된 요소 개수 계산

bit별로 가지고 있는 1의 개수를 미리 계산하는 방법을 통해 시간을 단축시킬 수 있습니다.

하지만 int의 크기인 32bit 전부의 경우를 계산할 경우 수십억 번의 계산이 필요하므로

시간초과가 발생합니다.

따라서 시간 내에 계산 가능한 크기만큼의 bit만을 사용하도록 제한해야 합니다.

 

아래 풀이의 경우 15bit로 제한합니다. 최대 134개의 int를 사용합니다.

 

풀이 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> bit_count(65536);

void setInitCount()
{
  bit_count[0] = 0;
  bit_count[1] = 1;
  bit_count[2] = 1;
  bit_count[3] = 2;
  int idx = 4;
  int step = 2;
  while (step < 16)
  {
    int loopCount = 1 << (step - 1);
    for (int i = 0; i < loopCount; i++)
    {
      bit_count[idx] = bit_count[idx - loopCount];
      idx++;
    }
    for (int i = 0; i < loopCount; i++)
    {
      bit_count[idx] = bit_count[idx - loopCount] + 1;
      idx++;
    }
    step++;
  }
}

int findCoFriend(int relationship1[], int relationship2[], int cursor)
{
  int result = 0;
  for (int i = 0; i <= cursor; i++)
  {
    int cofriend = relationship1[i] & relationship2[i];
    result += bit_count[cofriend];
  }
  return result;
}

int main()
{
  // freopen("input.txt", "r", stdin);
  setInitCount();
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int relationship[2001][126] = {};
  int cursor;
  for (int i = 1; i <= n; i++)
  {
    string relate;
    cin >> relate;
    cursor = 0;
    int idx = 0;
    for (int j = 0; j < n; j++)
    {
      if (relate[j] == '1')
      {
        relationship[i][cursor] |= (1 << idx);
      }
      idx++;
      if (idx > 15)
      {
        cursor++;
        idx = 0;
      }
    }
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++)
  {
    int a, b;
    cin >> a >> b;
    cout << findCoFriend(relationship[a], relationship[b], cursor) << '\n';
  }
  return 0;
}