(25.03.27) 비트 마스크의 활용 : DP 심화

Genie; 2025. 3. 27. 17:49

비트마스크가 생각보다 빠르게 적용할 수 있는 점을 알게 되어서 DP 부분에 많은 적용을 해보려고 노력하고 있다.

You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers.
For example, if nums = [1, 2, 3, 4]:[2, 3], [1, 2, 3], and [1, 3] are good subsets with products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively.[1, 4] and [4] are not good subsets with products 4 = 2*2 and 4 = 2*2 respectively.
Return the number of different good subsets in nums modulo 109 + 7.
A subset of nums is any array that can be obtained by deleting some (possibly none or all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 30

import java.util.*;

public class Solution {

    // 절대 불변할 문제의 조건들
    private static final int MOD = 1000000007;
    private static final int[] PRIMES = {2,3,5,7,11,13,17,19,23,29};

    public static int numberOfGoodSubsets(int[] nums) {

        // 소수 마스크를 생성 Map<소수인덱스, 해당 마스크>
        // 30이하의 수이기 때문에 미리 만들기
        Map<Integer, Integer> primeMasks = new HashMap<>();
        for(int i = 1; i <= 30; i++) {
             int mask  = 0;

            for(int j = 0; j < PRIMES.length; j++) {
                // 숫자는  소수로 나눠져야
                // 똑같은 소수로 두번 나눠지면 0 곧바로 break
                if( (i % PRIMES[j]) == 0) {
                    if( (i % (PRIMES[j]*PRIMES[j])) == 0) {
                        mask = 0;
                        break;
                    }
                    mask |= (1<<j);
                }
            }
            primeMasks.put(i, mask);
        }

        // nums  숫자
        int[] count = new int[31];
        for(int num : nums) {
            count[num]++;
        }

        // 중복제거 
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums) {
            numsSet.add(num); 
        }

        // DP 설정
        int[] dp = new int[1<<PRIMES.length];

        // 초기값 설정
        dp[0] = 1;

        // num 하나씩 반복하면서 DP에 넣기
        for(int num : numsSet) {
            int mask = primeMasks.get(num);

            // primeMask가 0 이면 그냥 넣지않기
            // num 에 없는  아니면 그냥 패스 
            if( mask == 0) continue;

            // 11111.. 에서 부터 하나씩 줄여가면서 진행 
             for(int j = (1 << PRIMES.length)-1 ; j >= 0; j--) {
                // 마스크가 겹칠때만 dp에 갱신 
                if( (mask & j) == 0) {
                    dp[mask | j] = (dp[mask | j] + (int)((long)dp[j] * count[num] % MOD)) % MOD;

                }
             }
        }

        // 숫자를 순차적으로 처리
        int result = 0;
        for (int i = 1; i < (1 << PRIMES.length); i++) {
            result = (result + dp[i]) % MOD;
        }

        // 숫자 1도 포함되어있다면 굿셋이기 때문에
        // 1이 포함된 것 반큼 result를 배로 늘려줘야함
        for(int i = 0; i < count[1]; i++) {
            result = ( result * 2 ) % MOD; 
        }

        return result;
    }
}

소수는 Constraint 조건이 30미만이므로 하드코딩 을 사용
GoodSet을 만들기 위한 조건으로 nums의 숫자가 소수의 제곱근 이상을 포함하고 있으면 안되는것을 검증하며, 검증이 될 경우, mask |= (1<<j);
- 즉, 2 3 5 7 … 과 같은 소수일 경우 해당 PRIMES 에서의 “인덱스” 만큼 1을 왼쪽으로 미룸
- 따라서, 2 는 1, 3은 10, 5는 100로 비트 마스크를 생성
int[] dp = new int[1<<PRIMES.length];
- DP 역시 소수의 길이 만큼 긴 비트 마스크를 채우게 됨 : 10000000000 개를 만들게 됨 ( 0 ~ 1111111111 인덱스 까지)
for(int j = (1 << PRIMES.length)-1 ; j >= 0; j--) {...
- 1111111111 인덱스 부터 하나씩 줄어가면서 점검
  - DP를 채울때, 비트 마스크를 진행하면서 이전것에서 더한 것을 채우는 것이기 때문에, 역뱡항으로 진행해
  - 정방향으로 계산하면 여러 값을 진행하면서 계속 갱신이 되면서 올라가기 때문에 중복 계산이 발생할 가능성이 있음

 if( (mask & j) == 0) {
    dp[mask | j] = (dp[mask | j] + (int)((long)dp[j] * count[num] % MOD)) % MOD; }

(mask & j) == 0
- number의 숫자 마스크인 mask 와 11111111111부터 내려가면서 정의된 패턴 j 랑 &연산 했을 때, j가 완전히 새로운 값일 때( 연산값이 0 일 때), dp를 갱신
- j에 해당하는 값을 추가할 수 있다는 의미
- 소수 중복 여부만 확신하는 조건 → 어차피 해당 j 값이 num에 없다면, 0이기 때문에 상관 없음
dp[mask | j] + (int)((long)dp[j] * count[num] % MOD)
- 캐스팅 이유
  - 값이 너무 커질 경우, 실제로 int 값을 초과해서 오버플로우 발생 → 반례가 실제로 발생 → long 으로 캐스팅을 한번 진행을 해야함
  - 반례 : nums = [2,17,8,1,30,26,6,2,5,10,28,15,11,15,25,24,24,13,23,27,23,24,20,1,25,1,21,23,10,21,12,14,13,26,18,21,12,14,26,8,16,11,21,8,9,5,3,25,2,14,23,23,16,8,19,5,9,26,17,15,15,17,9,18,25,14,10,30,20,21,23,19,11,21,25,8,25,1,5,17,30,4,6,2,22,18,10,18,30,12,8,6,18,23,22,4,23,27,23,27,19,11,25,20,30,16,29,1,22,26,19,2,13,8,19,23,3,27,20,18,11,2,23,3,5,16,3,23,22,7,24,25,16,13,5,17,24,14,10,19,11,29,8,16,5,14,8,26,15,7,3,11,19,12,27,24,1,6,4,16,8,7,25,12,21,20,15,25,29,6,25,5,28,10,3,27,19,12,1,13,22,5,13,5,18,6,2,10,24,7,14,7,26,10,4,17,4,24,6,5,5,1,7,5,14,18,23,10,20,7,2,28,15,30,16,8,24,11,2,4,13,10,29,11,20,8,3,17,8,4,26,26,5,16,30,7,7,22,22,14,3,29,20,17,27,2,20,23,1,7,4,16,9,15,15,23,8,11,14,18,12,3,26,27,13,17,20,27,11,5,14,12,18,19,21,20,4,27,5,17,19,5,1,18,22,16,8,29,21,3,20,17,3,15,29,4,27,2,10]
- count[num] 를 곱하는 이유
  - 중복이 되더라도 조합가능성 = 중복을 여러번 해야함 이기 때문에

위의 내용은 "조합에서 한번만 사용할 수 있는 모든 경우의 수" 라는 부분에서 비트마스크로 모든 조합을 계산하고 DP에 저장하는 알고리즘으로 작성할 수 있다.
또한 소수는 주어진 수 범위가 적을 경우, 하드 코딩을 사용하는 것이 오히려 빠르게 알고리즘을 작성할 수도 있다고 답안예제가 보여줘서 굳이 반복해서 소수 판별법 알고리즘을 굳이 사용하지 않고 쓰는것이 더 효율적일 수 있다고 했다.

저작자표시 비영리 변경금지 (새창열림)