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

풀이 아이디어

• n: 키의 개수
• m: 퀘스트 개수
• k: 퀘스트당 스킬 개수

각 퀘스트마다 사용한 스킬을 비트마스킹으로 표현해 int[] quest에 저장하고
재귀적으로 2n개의 키 중에서 n개를 고른 스킬 조합을 각각 구하고
각 조합마다 클리어 가능한 퀘스트 수를 계산해서 최대값을 구한다.
이때 모든 조합의 퀘스트 수를 계산하는 것을 재귀적으로 구한다.

배운 점

비트마스킹을 활용해서 필요한 이차원배열로 표현해야했던 조합을 1차원의 int[]로 표현했고
모든 가능한 경우의 수를 일일이 구하기보다는 재귀적으로 간단하게 구현할 수 있다는 걸 배웠다.

풀이 코드

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class _16457 {
    static int n, m, k, max = 0;
    static int[] quest; // 각 퀘스트가 가진 스킬
    static int usedSkills; // 모든 퀘스트에서 1번이상 사용된 스킬

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); // 키의 개수
        m = Integer.parseInt(st.nextToken()); // 퀘스트의 개수
        k = Integer.parseInt(st.nextToken()); // 퀘스트당 스킬의 개수

        quest = new int[m]; // 각 퀘스트가 가진 스킬
        usedSkills = 0; // 모든 퀘스트에서 1번이상 사용된 스킬

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < k; j++) {
                int skill = Integer.parseInt(st.nextToken());
                quest[i] |= (1 << (skill - 1));
                usedSkills |= (1 << (skill - 1));
            }
        }

        // System.out.println("quest: " + Arrays.toString(quest));
        // System.out.println("usedSkills: " + Integer.toBinaryString(usedSkills));

        // 인덱스0, key=0부터 시작해 n개의 스킬을 뽑는다.
        getMaxClearQuest(0,0,n); 

        System.out.println(max);
    }

    // 재귀적으로 n개의 스킬을 뽑아 클리어할 수 최대 퀘스트 수를 구한다.
    static void getMaxClearQuest(int idx, int key, int cnt) {
        // System.out.println("solve(" + idx + "," + key + "," + cnt + ")");
        if (cnt == 0) {
            int clear = 0;
            for (int i = 0; i < m; i++) {
                if ((quest[i] & key) == quest[i]) {
                    clear++;
                }
            }
            max = Math.max(max, clear);
            return;
        }

        for (int i = idx; i < 2 * n; i++) {
            getMaxClearQuest(i + 1, key | (1 << i), cnt - 1);
        }
    }
}