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

in Algorithm on 수학

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

풀이

처음에는 기타마다 연주할 수 있는 곡을 비트마스킹으로 체크하려고 했으나 곡의 개수가 최대 50까지 되기 때문에 int범위에서 비트마스킹을 할 수 없었다.

따라서 boolean 이차원 배열을 만들어 체크했다.

N개의 기타로 만들 수 있는 조합을 모두 만들어 연주할 수 있는 곡을 체크해줬다.

비트마스킹을 사용하려고 했던 것이 아쉬워 조합을 만들 때 비트마스킹을 이용했다.

for (int i = 1; i < (1 << N); i++) {
    int sel = 0;
    for (int j = 0; j < N; j++) {
        if ((i & (1 << j)) != 0) {
            sel |= (1 << j);
        }
    }

    countSong(sel);
}

1부터 2의 N제곱까지의 자연수 중 비트의 자리수가 1인 것이 선택된 기타이다.

메모리: 14548KB

시간: 136ms

언어: Java 11

코드

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

public class Main {

    static int N, M, max, ans;
    static boolean[][] guitar;

    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());

        guitar = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            String song = st.nextToken();

            for (int j = 0; j < M; j++) {
                if (song.charAt(j) == 'Y') {
                    guitar[i][j] = true;
                }
            }
        }

        max = 0;
        ans = -1;

        combi();

        System.out.println(ans);
    }

    private static void combi() {
        for (int i = 1; i < (1 << N); i++) {
            int sel = 0;
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) != 0) {
                    sel |= (1 << j);
                }
            }

            countSong(sel);
        }
    }

    private static void countSong(int sel) {
        boolean[] tmp = new boolean[M];
        for (int i = 0; i < N; i++) {
            if ((sel & (1 << i)) != 0) {
                for (int j = 0; j < M; j++) {
                    if (guitar[i][j]) {
                        tmp[j] = true;
                    }
                }
            }
        }

        int cnt = 0;
        for (int i = 0; i < M; i++) {
            if (tmp[i]) {
                cnt++;
            }
        }

        if (cnt == max) {
            ans = Math.min(ans, Integer.bitCount(sel));
        } else if (cnt > max) {
            max = cnt;
            ans = Integer.bitCount(sel);
        }
    }

}