[백준 9335] 소셜 광고 - JAVA

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

 

완탐 문제

 

비트마스킹 풀이

MAX_BIT => N길이의 1로 채워진 이진수 => 모든 사용자가 광고를 볼 때

bit[] => 정수 i를 선택했을 때 얻는 bit => i번째 사용자에 광고를 게시했을 때 볼 수 있는 친구들 및 자기 자신

compBit => 정수 n개를 뽑아 &연산 했을 때의 bit => 광고를 게시할 사람을 n명 뽑았을 때 광고를 본 사람들

 

i = 1 to MAX_BIT를 뽑는다.

k = 1 to N에 대해 i의 k번째 비트가 1이라면, bit[k]를 compBit에 or 연산한다.

 

diff => 뽑은 사람 개수 + 광고를 못본 사람 개수

i는 광고를 게시한 사람의 목록이니, bitCount를 diff에 누적한다.

N - ( compBit의 bitCount)로 광고를 보지못한 사람의 수를 구한다.

 

단, diff는 n명을 pick했을 때의 정답이 아닌 lower bound이다.

반례로 못본 사람이 3명 있을 때, 그 중 1명에게만 추가로 게시해도 3명이 전부 보는 경우도 있다. 이 경우 diff는 2만큼 더 작아질 수 있다.

 

이는, 어차피 완전탐색으로 사람을 뽑는 경우의 수를 모두 고려함으로서 상쇄된다.

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));
    int T = Integer.parseInt(br.readLine());

    while (T-- > 0) {
      int N = Integer.parseInt(br.readLine());

      int[] bit = new int[N + 1];
      for (int i = 1; i <= N; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        for (int j = 0; j < C; j++) {
          bit[i] |= 1 << (Integer.parseInt(st.nextToken()) - 1);
        }
        bit[i] |= 1 << (i - 1);
      }

      int MAX_BIT = (1 << N) - 1;
      int ans = Integer.MAX_VALUE;

      for (int i = 1; i <= MAX_BIT; i++) {

        int compBit = 0;
        int at = 1;
        
        for (int j = 1; j <= N; j++) {
          if ((i & at) == at) {
            compBit |= bit[j];
          }
          at <<= 1;
        }

        int diff = N - Integer.bitCount(compBit) + Integer.bitCount(i);

        ans = Math.min(ans, diff);
      }
      System.out.println(ans);
    }
  }
}