[BOJ 2128 // C++] 마지막 조별 시합

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2128번 문제인 마지막 조별 시합이다.
문제는 아래 링크를 확인하자.

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

 

$N$명 중 일부를 골랐을 때, $D$ 문제중 풀 수 있는 문제의 집합으로 나올 수 있는 경우의 수는 많아야 $2^D$가지임을 확인하자. 이러한 각 문제의 집합 중 원소가 $K$개 이하(풀 수 있는 문제의 수가 $K$개 이하)인 경우에 대하여 각 경우 포함할 수 있는 최대 인원을 $N$명을 직접 전부 살피는 식으로 확인해 문제를 해결하자.

 

특히, 집합의 원소가 $K$개인 경우만 살펴도 그 이하인 경우의 최대인원보다 항상 더 큰 값을 얻게 되므로 $K$개인 경우만 살펴도 충분히 문제를 해결할 수 있다. 이렇게만 살펴도 실제 그 집합의 모든 문제를 다 풀 수 있는 인원구성이 나오지 않는 경우(즉, 집합의 원소가 $K$개 미만인경우) 또한 전부 살피는 것과 같은 효과를 보임을 확인하자.

 

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

#include <iostream>
using namespace std;

int N, M, K;
int A[1000];
int ans;

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

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		int X; cin >> X;
		int &val = A[i];
		while (X--) {
			int x; cin >> x;
			val |= (1 << (x - 1));
		}
	}
	M = (1 << M);
	for (int i = 0; i < M; i++) {
		if (__builtin_popcount(i) == K) {
			int cnt = 0;
			for (int n = 0; n < N; n++) {
				if ((A[n] & i) == A[n]) cnt++;
			}
			ans = max(ans, cnt);
		}
	}

	cout << ans;
}