[PS] 백준 도전 숫자왕 java 풀이 (비트마스킹으로 모든 경우의 수 찾기)

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

 

문제 접근

• 숫자의 조합으로 만들 수 없는 수의 합을 구해야한다.
• 결국 만들 수 있는 모든 경우의 수를 구해야 하는데, N이 최대 20이면 최대 경우의 수는 2^20 이므로 DFS와 같은 방식은 시간 초과가 터진다.
• 따라서 다른 방식을 선택해야 한다. 그게 비트마스킹 방식이다.

비트마스킹으로 모든 경우의 수 찾기

        HashSet<Long> sumSet = new HashSet<>();
        int totalSubsets = 1 << N; // 2^N subsets
        for (int mask = 1; mask < totalSubsets; mask++) {
            long sum = 0;
            for (int i = 0; i < N; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum += numbers[i];
                }
            }
            sumSet.add(sum);
        }

 

• 1 << N:  모든 경우의 수를 저장하는 정수이다. 예를 들어, N이 3이면 이진수로 1000 이므로 8가지이다.
• 각 이진수 자리에 마스크를 넣어본다. mask 변수의 각 비트는 숫자를 포함할지 여부를 나타낸다. 비트 1이면 해당 숫자를 포함하고, 0이면 포함하지 않는다. 문제에서는 모두 자연수라는 조건 때문에 0을 제외해야 하므로 1부터 시작한다.
• i = 0부터 N까지 순회하며, 즉 각 이진수의 자릿수를 순회한다.
• ((mask & (1 << i)) != 0)의 연산:
  • 1 << i:
    • 특정 위치의 비트가 1인 값을 생성한다.
    • 예를 들어, i = 2일 때:
      • 1 (이진수: 0001)을 왼쪽으로 두 칸 이동한다.
      • 결과: 0100
  • mask & (1 << i):
    • mask의 i번째 비트가 1인지 확인한다.
    • AND 연산을 수행하여 mask의 i번째 비트만 검사한다.
    • 예:
      • mask = 0110 (10진수로 6), i = 2
      • 1 << i = 0100
      • 연산: 0110 & 0100 = 0100 (결과는 0이 아니므로 i번째 비트가 1)
  • 결과 확인:
    • mask & (1 << i)의 결과가 0이 아니면, mask의 i번째 비트가 1이라는 뜻이다.
    • 결과가 0이면, i번째 비트는 0이다.
• 비트가 1이면 부분 집합에 포함되므로 합에 더한다. 그리고 HashSet에 총합을 저장한다.
• HashSet 안에  합이 1 이상이고, M이하이면 count++ 
• M - count, 즉 모든 만들 수 있는 숫자의 수와 만들어진 총합의 수를 빼면 못 만드는 수의 개수이다.

예제: 입력: numbers = [1, 3, 4] mask = 5

비트별 동작 분석

• mask = 5의 이진수는 101이다.
• 배열의 각 인덱스 iii에 대해 다음을 수행:
  • i=0: mask & (1 << 0) = 101 & 001 = 001 (포함: numbers[0] = 1)
  • i=1: mask & (1 << 1) = 101 & 010 = 000 (미포함)
  • i=2: mask & (1 << 2) = 101 & 100 = 100 (포함: numbers[2] = 4)

결과:

mask = 5는 {1, 4}라는 부분 집합을 나타낸다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] numbers = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        long M = 0;
        for (int i = 0; i < N; i++) {
            numbers[i] = Long.parseLong(st.nextToken());
            M += numbers[i];
        }

        HashSet<Long> sumSet = new HashSet<>();

        int totalSubsets = 1 << N; // 2^N subsets
        for (int mask = 1; mask < totalSubsets; mask++) {
            long sum = 0;
            for (int i = 0; i < N; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum += numbers[i];
                }
            }
            sumSet.add(sum);
        }

        long count = 0;
        for (long sum : sumSet) {
            if (sum >= 1 && sum <= M) {
                count++;
            }
        }

        System.out.println(M - count);
    }
}