[백준] 1182번 부분집합 비트마스크로 풀어보기 : Programming Story

1. 백준 문제 소개

1) 링크

www.acmicpc.net/problem/1182

2) 문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

3) 입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

4) 출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

더 자세한 문제 제한을 보기 위해서는 위 링크를 타고 들어가보자.

2. 풀이

비트마스크란 비트연산을 사용하여 정수로 집합을 나타내는 것이다.

예를 들어 {1,3,4,5,9} 가 사용이 되었다면 우리는 이를 정수로 01000111010 이라고 표현할 수 있다. (binary digit이 0자리부터 시작한다고 생각했을 때, 1번째 자리, 3번째자리, 4번째 자리, 5번째 자리, 9 번째 자리를 1로 표시하는 것이다)

그러면 이 문제도 비트마스크로 풀어보자.

각각의 숫자를 입력받고, 그 숫자가 부분집합에 포함되면 해당 자리수가 1, 포함되지 않으면 해당 자리수를 0이라고 생각하는 것이다.

먼저 비트마스크를 처리한 코드부분만 살펴보자.

 for(int i=1; i<(1<<n); i++){
            int sum=0;
            for(int k=0; k<n; k++){
                if ((i&(1<<k))!=0){
                    sum+=a[k];
                }
            }
            if (sum==s){
                ans++;
            }
        }

이렇게 구할 수 있는데 for문을 1부터 1<<n전까지 처리한 이유에 대해서 생각해보자.

우선 0부터 처리하지 않은 이유는 공집합을 제외한다고 문제에서 나와 있기 때문이다.

그리고 비트마스크로 n자리를 처리하면 0부터 (1<<n)-1자리까지 가능하다. 총 n개의 숫자에 대해서 0부터 n-1자리가 모두 다 부분집합에 포함된다면 각 자리수가 모두 1이 되어서 (1<<n)-1라는 최댓값이 나온다.

따라서 가능한 모든 경우에 대해서 inner for문이 0부터 n-1자리까지 돌면서 해당 자리의 수가 1이라면 부분집합에 포함되었다는 말이기 때문에 이를 sum에다가 추가한다.

최종적으로 sum이 문제에서 주어진 합과 같다면 답을 찾은 것이므로, 답의 개수에 1을 더해주게 된다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int s=sc.nextInt();
        int [] a=new int [n];
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
        }
        int ans=0;
        for(int i=1; i<(1<<n); i++){
            int sum=0;
            for(int k=0; k<n; k++){
                if ((i&(1<<k))!=0){
                    sum+=a[k];
                }
            }
            if (sum==s){
                ans++;
            }
        }
        System.out.println(ans);
    }
}

종합적으로 코드를 살펴보면 위와 같이 구할 수 있다.