[Java] 백준 BOJ / 1497번: 기타콘서트

기타콘서트

문제

---

문제 설명

기타들이 N개 주어지고 각 기타들이 어떤 곡을 칠 수 있는지 주어진다.

이러한 기타들을 조합해서 최대한 많은 곡을 연주하고 싶을 때 필요한 최소의 기타의 수를 구하는 문제이다.

---

구현

비트마스킹을 사용해서 모든 조합의 수를 구한다.

예제에서 주어진 4개의 기타를 사용한다면 나올 수 있는 조합의 수는 다음과 같다.

0000,
0001, 0010, 0100, 1000,
0011, 0110, 0101, 1001, 1010, 1100, 0111, 1101, 1011, 1110,
1111

이렇게 나온 조합은 각 인덱스의 기타의 사용여부를 뜻한다.

이렇게 나온 조합별로 기타의 곡을 조합해서 나올 수 있는 경우의 수를 세서 최대 연주할 수 있는 곡을 최신화 해주고 그 때마다 기타가 몇개 쓰였는지 확인해주면 된다.

일단 기타의 정보를 저장해줄 arr라는 배열을 사용해서 각 기타가 칠 수 있는 곡들을 비트로 표현해준다.

for (int idx = 0; idx < n; idx++){
	st = new StringTokenizer(br.readLine());
	st.nextToken();
	String str = st.nextToken();
	StringBuilder sb = new StringBuilder();

	//기타 길이
	for (int i = 0; i < str.length(); i++) {
		sb.append(str.charAt(i) == 'Y' ? "1" : "0");
	}

	arr[idx] = String.valueOf(sb);
}

이제는 어떤 기타를 칠 지 정해주어야 한다.
모든 조합을 확인하기 위해 mask 라는 변수를 1부터 최대 2^n 까지 정해주면 된다.

그리고 어떤 노래를 연주할 수 있는지 확인하는 songMask 변수와 총 몇개의 기타를 사용했는지 확인하는 guitarCount 변수를 선언한다.

//각 기타에 대해서 확인
for (long mask = 1; mask < (1L << n); mask++) {
	long songMask = 0;
    int guitarCount = 0;
	//코드 구현
}

mask 변수로 현재 어떤 기타가 선택되었는지 확인 할 수 있으니 이제 이 기타들로 연주할 수 있는 곡을 확인해주어야한다.

각 mask에 대해서 기타의 개수만큼 루프변수 i를 늘려주면서 해당 기타가 켜져있는지 확인하고 켜져 있다면 0으로 초기화 되어있는 songMask 변수와의 OR 연산을 통해 초기화해주고 guitarCount 를 늘려준다.

//각 기타에 대해서 확인
for (long mask = 1; mask < (1L << n); mask++) {
	//i 번째 기타가 켜져 있다면
    for(int i = 0; i < n; i++) {
		if ((mask & (1L << i)) != 0) {
          //i번째 기타랑 OR 연산을 통해 나올 수 있는 곡의 개수 확인
          songMask |= Long.parseLong(arr[i], 2);
          guitarCount++;
    	}
	}
}

그리고 bitCount 함수를 사용하여 songCount를 세주고 maxSongCount와 minGuitarCount를 최신화 해주면 된다.

---

코드

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

public class Main_1497 {
  static int n, m;
  static String[] arr;
  static int maxSongCount = -1;
  static int minGuitarCount = Integer.MAX_VALUE;
  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 String[n];

    for (int idx = 0; idx < n; idx++){
      st = new StringTokenizer(br.readLine());
      st.nextToken();
      String str = st.nextToken();
      StringBuilder sb = new StringBuilder();

      //기타 길이
      for (int i = 0; i < str.length(); i++) {
        sb.append(str.charAt(i) == 'Y' ? "1" : "0");
      }

      arr[idx] = String.valueOf(sb);
    }

    //조합 확인 1 ~ n 까지 2진수로 백트래킹
    for (long mask = 1; mask < (1L << n); mask++) {
      long songMask = 0;
      int guitarCount = 0;

      //각 기타에 대해서
      for (int i = 0; i < n; i++) {
        //i번째 기타가 켜져 있으면
        if ((mask & (1L << i)) != 0) {
          //i번째 기타랑 OR 연산을 통해 나올 수 있는 곡의 개수 확인
          songMask |= Long.parseLong(arr[i], 2);
          guitarCount++;
        }
      }

      //bitCount로 몇개 칠 수 있는지 확인
      int songCount = Long.bitCount(songMask);
      if (songCount > maxSongCount) {
        maxSongCount = songCount;
        minGuitarCount = guitarCount;
      } else if (songCount == maxSongCount) {
        minGuitarCount = Math.min(minGuitarCount, guitarCount);
      }
    }
    System.out.println(maxSongCount == 0 ? -1 : minGuitarCount);
  }
}