[백준 30237] 합집합 (c++) Codeforces Round 899 (Div. 2) B번

1. 문제

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

코드포스 Round899 B번 문제입니다.

2. 풀이

차집합 계산하기

U = S1 ∪ S2 ∪ S3 ∪ ... ∪ Sn 이라고 해봅시다. 먼저 우리가 구하는 S는 완전탐색으로 생각해볼 수 있습니다. S₁부터 Sn까지 모든 부분집합을 Subset이라고 하면, 모든 Subset에 대해서 U - Subset을 비교하는 방법입니다. 즉,  전체합집합과의 차집합을 비교하는 것으로 생각할 수 있습니다. 하지만 Subset을 모두 탐색하면 O(2ⁿ)이므로 시간초과가 발생합니다.

따라서 전체집합에서 원소를 하나씩 빼보는 방식을 생각했습니다. x ∈ U인 임의의 x에 대해 U - x를계산하면  x를 가지고 있는 모든 Si도 빠져야 합니다. 예를 들어 test case 1을 살펴보겠습니다.

4(입력할 Si의 개수)
3 1 2 3 → S1 = {1, 2, 3}
2 4 5 → S2 = {4, 5}
2 3 4 → S3 = {3, 4}
3 1 4 5 → S4 = {1, 4, 5}

위의 입력에서 U = {1, 2, 3, 4, 5}가 됩니다. 만약 x = 3인경우 차집합 U - x를 고려한다고 하면 3을 포함하는 S1, S3이 모두 빠집니다. 따라서 x = 3인 경우 우리가 구하는 S =  U - (S1 ∪ S3) = S2 ∪ S4가 됩니다.

위처럼 합집합 U를 미리 구해놓고 모든 x에 대해 비교하면  O(Nx)의 시간복잡도로 충분히 해결할 수 있습니다. 마치 U의 집합을 비둘기집처럼 생각하고 원소를 기준으로 탐색하는 비둘기집 원리처럼 생각할 수 있습니다.

 

비트마스킹

집합의 표현방법을 2차원 배열로 해도 되지만 비트마스킹을 이용하면 훨씬 간단하고 빠르게 구현할 수 있습니다. 특히나 합집합, 차집합 등은 |(OR), &(AND)연산을 이용하여 O(1)에 계산할 수 있습니다.

 

3. 구현

비트마스킹을 이용하여 원소마다 차집합을 비교하며 S의 최솟값을 구하는 코드입니다. 다음 몇 가지를 주의해야 합니다.

• 집합의 원소가 50개이므로 64비트 long long 자료형으로 비트를 표현해야 합니다.
• 비트이동 과정에서 (1 << k)가 아니라 (1LL << k)처럼 연산 과정에서도 overflow를 신경써야 합니다.
• test case마다 state, ans 등이 달라지므로 초기화해주어야 합니다.

#include<iostream>
#include<cstring>

using namespace std;

int N, M, T, ans;
long long state[51];

int bitCount(long long x) {
	int ret = 0;
	for (int i = 0; i < 50; i++) {
		ret += (x >> i) & 1;
	}
	return ret;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> T;
	while (T--) {
		memset(state, 0, sizeof(state));
		long long Union = 0;

		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> M;
			for (int j = 0; j < M; j++) {
				long long x;
				cin >> x;
				state[i] |= (1LL << (x -1));
				Union |= (1LL << (x - 1));
			}
		}

		//solve
		ans = 0;
		for (int i = 0; i < 50; i++) {
			long long cmb = 0;
			long long x = (1LL << i);
			for (int j = 0; j < N; j++) {
				if (x & state[j]) continue;
				cmb |= state[j];
			}
			int cmb_siz = bitCount(cmb);
			int Union_siz = bitCount(Union);
			if (cmb_siz < Union_siz) ans = max(ans, cmb_siz);
			//else ans = 0;
		}
		cout << ans << "\n";
	}
}