백준 11578번 - 팀원 모집 java

 

문제

2015년 11월 28일은 기다리고 기다리던 제1회 IUPC가 열리는 날이다. IUPC는 Inha University Programming Contest의 약자로 인하대학교 IT공대 학부생이면 누구나 참여할 수 있는 프로그래밍 경시대회이다.

IUPC의 총상금은 무려 110억 원이나 되며 고급스러운 점심과 많은 다과가 제공되어 참가자들이 대회에 집중할 수 있도록 최적의 환경을 제공한다. 그중 참가자들을 진정 열광시키는 것은 수많은 팀에게 추첨을 통해 문화상품권을 나눠준다는 점이다.

컴퓨터정보공학과에 재학 중인 강호는 대회에 참가하기 위해 팀원을 모집하려고 한다. IUPC가 여타 많은 대회와 다른 점이 있다면 문제의 수가 많고 팀원의 수가 무제한이라는 것이다. IUPC에서 모든 문제를 다 풀어 우승한 뒤 엄청난 부와 명예를 챙기고 싶은 강호는 모든 문제를 풀 수 있는 팀을 만들고 싶어 한다. 하지만 팀원의 수가 많으면 많을수록 자신에게 돌아오는 상금이 적어지기 때문에 최소한의 팀원으로 대회를 우승하고 싶어 한다.

강호가 선택할 수 있는 팀원의 목록과 각각의 팀원들이 해결할 수 있는 문제의 번호들이 주어졌을 때 강호가 IUPC에서 최소한의 팀원으로 모든 문제를 다 풀어 우승할 수 있도록 팀을 만들어보자.

---

입력

첫 번째 줄에 문제의 수 N과 강호가 팀원으로 고를 수 있는 학생들의 수 M이 공백을 구분으로 차례대로 주어진다. N과 M은 1이상 10이하의 자연수이다.

두 번째 줄부터 M개의 줄에 차례대로 i(1 ≤ i ≤ M)번 학생들이 풀 수 있는 문제의 개수 Oi와 i번 학생이 풀 수 있는 문제의 번호 Pij(1 ≤ j ≤ Oi, 1 ≤ Pij ≤ N)가 Oi개 주어진다.

---

출력

모든 문제를 풀 수 있으면서 팀원의 수가 가장 적은 팀을 구해 팀원의 수를 출력한다. 만약 모든 문제를 풀 수 있는 팀을 만들 수 없다면 -1을 출력한다,

---

해결 방법

모든 문제를 풀 수 있는 최소의 학생 수를 찾아야 한다. 이 때 학생 수는 10명으로, 학생을 고르는 경우의 수는 2^10 = 1024 가지가 나온다. 물론 한 명도 고르지 않는다면 문제를 풀지 못하기 때문에 실제론 1023가지다.

 

학생 조합 구하기

학생을 고르는 경우의 수가 매우 적기 때문에, 재귀함수로 브루트 포스를 구현해 조합을 생성했다.

 

static void solution(int M, int start, int count, int number) {
    if (canCompleteAll(number)) {
        min = Math.min(min, count);
        return;
    }
    for (int i = start; i <= M; i++) {
    	//이번 학생을 고른 경우의 수를 탐색
        solution(M, i + 1, count + 1, number | arr[i]);
        //이번 학생을 고르지 않은 경우의 수를 탐색
        solution(M, i + 1, count, number);
    }
}

 

문제 다 풀 수 있는지 검사

문제의 수도 10가지로 매우 적기 때문에, 비트 마스킹을 이용해 모든 문제를 다 풀었을 때의 수를 구할 수 있다. 예를 들어 문제의 개수가 10개라 했을 때, 비트로 표현하면 다음과 같이 표현할 수 있다. = 11111111110 <- 비트의 각 자리수 i는 i번째 문제를 풀었는지 여부를 나타낸다. 1이면 풀 수 있고, 0이면 풀 수 없다.

 

따라서 우선 문제를 다 풀 수 있는 수를 비트마스킹을 통해 구한다.

 

static void initAnswer(int N) {
    for (int i = 1; i <= N; i++) {
        answer |= 1 << i;
    }
}

그 다음 학생이 풀 수 있는 문제를 처리해야 하는데, 학생이 풀 수 있는 문제도 비트 마스킹을 통해 하나의 정수로 쉽게 관리할 수 있다.

 

예를 들어 1번 학생이 2 3 4 5 번 문제를 푼다고 가정했을 때 이를 111100 으로 표현할 수 있고, 2번 학생이 1, 2번 문제를 푼다고 가정했을 때 이를 110이라고 표현할 수 있다.

 

따라서 학생이 풀 수 있는 문제가 들어올 때마다 or 연산을 사용해 정수를 관리해준다.

 

for (int i = 1; i <= M; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    st.nextToken();
    while (st.hasMoreTokens()) {
        arr[i] |= 1 << Integer.parseInt(st.nextToken());
    }
}

 

이제 학생을 고를 때마다 or 연산을 통해 풀 수 있는 문제를 추가해가며, 모든 문제를 풀 수 있다고 했을 때 고른 학생 수를 비교한 뒤 최소값을 갱신시킨다.

 

 

전체 코드

package per.november.gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.System.in;

public class P11578 {
    static int[] arr;
    static int answer = 0;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer input = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(input.nextToken());
        int M = Integer.parseInt(input.nextToken());

        arr = new int[M + 1];
        initAnswer(N);

        for (int i = 1; i <= M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            st.nextToken();
            while (st.hasMoreTokens()) {
                arr[i] |= 1 << Integer.parseInt(st.nextToken());
            }
        }

        solution(M, 1, 0, 0);
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }

    static void initAnswer(int N) {
        for (int i = 1; i <= N; i++) {
            answer |= 1 << i;
        }
    }

    static void solution(int M, int start, int count, int number) {
        if (canCompleteAll(number)) {
            min = Math.min(min, count);
            return;
        }
        for (int i = start; i <= M; i++) {
            solution(M, i + 1, count + 1, number | arr[i]);
            solution(M, i + 1, count, number);
        }
    }

    static boolean canCompleteAll(int number) {
        return number == answer;
    }
}