[백준 09335] 소셜 광고 [Java]

문제

9335번: 소셜 광고

9335번: 소셜 광고

 

---

풀이

문제 요약

최소한의 사용자에게만 광고를 게시해, 전체 사용자들이 광고를 모두 볼 수 있도록 하자.

아이디어

N개의 줄에 걸쳐 i번째 사용자의 친구 d명의 번호가 주어진다.

이중에서 최소한의 사용자를 선택해 전체 N명에게 광고를 게시해야 한다.

사용자와 친구를 비트마스킹으로 표현하자.

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

                // Solve
                friend[i] = 1 << i;
                for (int j = 0; j < d; j++) {
                    friend[i] |= 1 << (Integer.parseInt(st.nextToken()) - 1);
                }
            }

광고를 게시할 임의의 사용자(select)를 선택하고, 선택된 사용자의 친구들을 모두 합쳤을 때, N명 모두에게 광고를 게시할 수 있는지 확인하자.

광고를 게시할 임의의 사용자가 최소가 되도록 결과를 갱신하면 된다.

            int res = N;
            for (int select = 1; select < (1 << N); ++select) {
                int cnt = 0;
                int check = 0;
                for (int i = 0; i < N; i++) {
                    if ((select & (1 << i)) != 0) {
                        check |= friend[i];
                        ++cnt;
                    }
                }

                if (check == (1 << N) - 1) {
                    res = Math.min(res, cnt);
                }
            }

풀이시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/09335.java

problem-solving/baekjoon-online-judge/easy/09335.java at main · rogi-rogi/problem-solving