문제링크

풀이1

DFS를 사용한 브루트포스

1. 연주할 수 있는 노래를 체크하는데에 비트마스킹을 사용한다.
   입력으로 주어지는 각 기타로 연주할 수 있는 노래 문자열을 long형으로 변환한다.
   'Y'는 1로, 'N'은 0으로 치환하여 나온 결과(이진수)를 십진수로 변환한다.

    public static long strToLong(String song) {
        long sum = 0;
        for (int i = 0; i < m; i++) {
            char key = song.charAt(i);
            if (key == 'Y') {
                sum += 1L << i;
            }
        }
        return sum;
    }

2. 완전 탐색으로, 모든 조합을 확인하며 노래를 최대한 많이 연주하였을 때, 최소의 기타 개수를 구한다.
   완전 탐색시, dfs를 사용하여 해당 순번의 기타로 연주하였을 때, 연주하지 않았을 때로 나누어 dfs를 수행해준다.현재 기타를 선택하는 경우는, 해당 기타가 연주 가능한 노래와 지금까지 연주 가능한 노래를 or 연산하여 연주 가능한 노래를 갱신해준다.

    /**
     *
     * @param guitarList: 기타 목록
     * @param idx: 선택할 기타의 인덱스
     * @param playedSong: 지금까지 선택한 기타들로 연주 가능한 노래 bit
     * @param guitarCnt: 선택한 기타 수
     */
    public static void func(ArrayList<Guitar> guitarList, int idx, long playedSong, int guitarCnt) {
        int played = Long.bitCount(playedSong); //  1의 개수를 카운트 -> 지금까지 연주 가능한 노래 수
        if (played == maxSong && minGuitar > guitarCnt) {   //  연주 가능한 노래 수가 최대와 같고, 선택한 기타 수는 더 적을 경우
            minGuitar = guitarCnt;
        }
        if (played > maxSong) { //  연주 가능한 노래 수가 최대보다 클 경우
            maxSong = played;
            minGuitar = guitarCnt;
        }
        if (idx == n || played == m) {  //  마지막 기타까지 탐색 완료했거나, 모든 노래를 연주 가능하다면 종료
            return;
        }

        //  현재 기타를 선택할 경우
        func(guitarList, idx + 1, playedSong | guitarList.get(idx).playableSongs, guitarCnt + 1);
        //  현재 기타를 선택하지 않고 건너뛰는 경우
        func(guitarList, idx + 1, playedSong, guitarCnt);
    }

코드1

package BOJ;

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

public class sol1497 {
    static int n, m;
    static int minGuitar = Integer.MAX_VALUE;
    static int maxSong = Integer.MIN_VALUE;

    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());
        ArrayList<Guitar> guitarList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            guitarList.add(new Guitar(st.nextToken(), strToLong(st.nextToken())));
        }
        func(guitarList, 0, 0, 0);
        System.out.println(maxSong == 0 ? -1 : minGuitar);
    }

    /**
     *
     * @param guitarList: 기타 목록
     * @param idx: 선택할 기타의 인덱스
     * @param playedSong: 지금까지 선택한 기타들로 연주 가능한 노래 bit
     * @param guitarCnt: 선택한 기타 수
     */
    public static void func(ArrayList<Guitar> guitarList, int idx, long playedSong, int guitarCnt) {
        int played = Long.bitCount(playedSong); //  1의 개수를 카운트 -> 지금까지 연주 가능한 노래 수
        if (played == maxSong && minGuitar > guitarCnt) {   //  연주 가능한 노래 수가 최대와 같고, 선택한 기타 수는 더 적을 경우
            minGuitar = guitarCnt;
        }
        if (played > maxSong) { //  연주 가능한 노래 수가 최대보다 클 경우
            maxSong = played;
            minGuitar = guitarCnt;
        }
        if (idx == n || played == m) {  //  마지막 기타까지 탐색 완료했거나, 모든 노래를 연주 가능하다면 종료
            return;
        }

        //  현재 기타를 선택할 경우
        func(guitarList, idx + 1, playedSong | guitarList.get(idx).playableSongs, guitarCnt + 1);
        //  현재 기타를 선택하지 않고 건너뛰는 경우
        func(guitarList, idx + 1, playedSong, guitarCnt);
    }

    public static long strToLong(String song) {
        long sum = 0;
        for (int i = 0; i < m; i++) {
            char key = song.charAt(i);
            if (key == 'Y') {
                sum += 1L << i;
            }
        }
        return sum;
    }

    public static class Guitar {
        String name;
        long playableSongs;

        Guitar(String name, long playableSongs) {
            this.name = name;
            this.playableSongs = playableSongs;
        }
    }
}

풀이2

비트마스킹을 이용한 브루트포스

n개의 기타가 있으므로 가능한 조합은 $2^n$ 가지
이를 비트마스크로 나타내면, 1 << n

1부터 (1 << n) - 1까지 모든 조합을 탐색하며 노래를 최대한 많이 연주하였을 때, 최소의 기타 개수를 구한다.

코드2

package BOJ;

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

public class sol1497_2 {
    static int n, m;
    static int minGuitar = Integer.MAX_VALUE;
    static int maxSong = Integer.MIN_VALUE;

    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());
        ArrayList<Guitar> guitarList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            guitarList.add(new Guitar(st.nextToken(), strToLong(st.nextToken())));
        }

        int mask = 1 << n;
        for (int i = 1; i < mask; i++) {    //  각 조합을 전부 탐색
            int guitarCnt = Integer.bitCount(i);
            int songCnt = 0;
            long playedSongs = 0;
            for (int j = 0; j < n; j++) {   //  사용된 기타로 연주 가능한 곡 탐색
                if ((i & 1 << j) != 0) {
                    Guitar guitar = guitarList.get(j);
                    playedSongs |= guitar.playableSongs;
                }
                songCnt = Long.bitCount(playedSongs);
            }
            if (songCnt == maxSong && guitarCnt < minGuitar) {
                minGuitar = guitarCnt;
            }
            if (songCnt > maxSong) {
                minGuitar = guitarCnt;
                maxSong = songCnt;
            }
        }

        System.out.println(maxSong == 0 ? -1 : minGuitar);
    }

    public static long strToLong(String song) {
        long sum = 0;
        for (int i = 0; i < m; i++) {
            char key = song.charAt(i);
            if (key == 'Y') {
                sum += 1L << i;
            }
        }
        return sum;
    }

    public static class Guitar {
        String name;
        long playableSongs;

        Guitar(String name, long playableSongs) {
            this.name = name;
            this.playableSongs = playableSongs;
        }
    }
}