[백준 1887] Cow Pizza - JAVA

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

 

비트마스킹 문제

 

i for 0 to MAX(== 0bT):

   bit for 0 to N - 1: 까지 탐색하며,

 [i AND bit != bit]를 만족하는 i 개수를 찾는 문제다.

 

문제 유형만 깨달으면 구현은 쉬웠고, 소가 진짜로 피자를 좋아하는진 모르겠다.

 

 

+ 흥미로운 내용 : bit 배열 오름차순 정렬하면, 앞의 원소가 뒤의 원소에 포함될 확률이 높아지므로 약간의 성능향상을 노려볼 수 있다.

 

 

 

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

class Main {

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int ans = 0;
    int T = Integer.parseInt(st.nextToken());
    int MAX = (1 << T) - 1; // T <= 20, 0b20 == 1048575
    int N = Integer.parseInt(st.nextToken());
    int[] a = new int[N];

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      int S = Integer.parseInt(st.nextToken());

      for (int j = 0; j < S; j++) {
        a[i] |= 1 << (Integer.parseInt(st.nextToken()) - 1);
      }
    }

    for (int i = 0; i <= MAX; i++) {
      boolean b = true;
      for (int bit : a) {
        if ((i & bit) == bit) {
          b = false;
          break;
        }
      }

      if (b) {
        ans++;
      }
    }
    System.out.println(ans);
  }
}