백준 2128: 마지막 조별 시합

문제 요약

학생들은 지금 치르고 있는 모의고사가 마지막일 것으로 생각하고 있겠지만, 모의고사가 끝난 뒤에는 사실 마지막 조별 시합이 있다. 마지막 조별 시합에서는 A조와 B조의 두 개의 조로 나뉘어 시합을 하게 되는데, 이번에는 각 학생들이 잘 푸는 알고리즘 문제에 따라서 조를 나누기로 하였다.

학생들은 총 N(1 ≤ N ≤ 1,000)명이 있고, 알고리즘 문제의 종류는 D(1 ≤ D ≤ 15)종류이다. 조를 나눌 때에는 학생들의 점수가 어느 정도가 되도록 해야 하기 때문에, A조 학생들이 풀 수 있는 서로 다른 문제들의 총 가짓수가 K(1 ≤ K ≤ D)개 이하가 되도록 하려 한다. 이 기준을 만족하도록 A조를 뽑고, 나머지 학생들을 B조에 넣으려 한다. 조별 시합에서는 조별 토론 시간이 있기 때문에, 그 조에 있는 학생들 중 한 명이라도 문제를 풀 수 있으면 나머지 학생들도 문제를 풀 수 있게 된다.

이러한 조건으로는 A조와 B조의 우열을 바로 알기 힘들기 때문에, 우선 A조가 최대 몇 몇까지 가능한지를 알아보려 한다. 학생들에 대한 정보가 주어졌을 때, A조의 최대 인원수를 구하는 프로그램을 작성하시오.

문제 분류

• 수학
• 브루트포스 알고리즘
• 조합론
• 비트마스킹

문제 풀이

조합의 문제이다. 각 학생들의 조합으로 최대 몇 개의 문제를 풀 수 있는가?로 접근하면 안 된다. 1000명의 조합을 표현하기 어렵기 때문이다. 이에 각 d개 문제의 조합 별로 최대 몇 명이 풀 수 있는가? 로 접근해야 한다.
각 학생마다 풀 수 있는 문제를 비트마스킹으로 표현하고, d개 에서 k개를 골라 문제의 조합을 완성한 뒤, 해당 문제를 풀 수 있는 학생의 수를 카운팅한다. 단, 고른 k개의 문제 외의 문제도 풀 수 있는 학생은 제외한다. 문제를 0개 풀 수 있는 학생은 따로 카운팅하여 정답에 더해주었다.

풀이 코드

import java.util.*;
import java.io.*;

public class Main {	
	static int ary[];
	static int n, d, k;
	static int res;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int cnt = 0, m;
		
		n = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		ary = new int[n];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			if(m == 0) cnt++;
			while(m-- > 0)
				ary[i] |= (1 << (Integer.parseInt(st.nextToken()) - 1));
		}
		dfs(0, 0, 0);
		System.out.println(res + cnt);
	}
	
	static void dfs(int idx, int state, int cnt) {
		if(d - idx + cnt < k)
			return;
		if(cnt >= k) {
			int sum = 0;
			for(int i = 0; i < n; i++) {
				if((ary[i] & state) > 0 && Integer.bitCount(ary[i] | state) == k)
					sum++;					
			}
			res = Math.max(res, sum);
			return;
		}
		
		if(idx < d) {
			dfs(idx + 1, state, cnt);
			dfs(idx + 1, state | (1 << idx), cnt + 1);
		}
    }
}