[백준 1497] 기타콘서트 - JAVA

BOJ Link

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

 

풀이 과정

일반적인 부분집합 + 브루트포스로 풀 수 있다.

 

문제에서 N <= 10이므로, 부분집합을 구하는데 최대 O(2^10) 이다.

 

또한, 다음과 같은 최적화를 할 수 있다. 입력 범위가 작아서 나는 쓰지 않았다.

 

1. A기타가 B기타가 칠 수 있는 곡을 모두 포함한다면 (B가 A의 부분집합이면), B기타를 탐색에 고려할 필요가 없다.

 

2. 백트래킹

비트마스킹을 쓸 때, 탐색 중인 기타와 OR 연산을 해도 bitCount(= 연주할 수 있는 곡 수) 가 같다면 제외한다.

 

(1번과 같은 논리이다. 현재까지 탐색한 기타들이 A가 되고, 탐색 중인 기타가 B가 된다.)

 

(마찬가지로, 현재까지 어떤 기타들을 포함했는지 기록하지 않아도 된다. 어차피 B(부분집합)가 되면서 알아서 제외한다.)

 

제출 코드

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

class Main {
    static int N, M, ans, ansG;
    static boolean[][] arr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            String s = st.nextToken();
            for (int j = 0; j < M; j++) {
                arr[i][j] = s.charAt(j) == 'Y';
            }
        }
        subset(0, 0, new boolean[N]);
        System.out.println(ans == 0 ? -1 : ansG);
    }

    public static void subset(int dep, int guitar, boolean[] pick) {

        if (dep == N) {
            boolean[] song = new boolean[M];

            for (int i = 0; i < N; i++) {
                if (pick[i]) {
                    for (int j = 0; j < M; j++) {
                        if (arr[i][j]) song[j] = true;
                    }
                }
            }

            int now = 0;
            for (boolean b : song) if (b) now++;

            if (now == ans) {
                ansG = Math.min(ansG, guitar);
            } else if (now > ans) {
                ans = now;
                ansG = guitar;
            }

            return;
        }


        pick[dep] = true;
        subset(dep + 1, guitar + 1, pick);
        pick[dep] = false;
        subset(dep + 1, guitar, pick);
    }


}