[백준] 1182번 부분집합의 합

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q1182_Bit.java (비트 마스크)
Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q1182.java (재귀)

N개의 원소를 가진 집합이 주어진다. S가 주어질 때 이 집합들의 부분집합의 원소의 합이 S가 되는 경우를
출력하여라. 공집합은 개수에 포함하지 않는다.

처음 생각

주어진 집합에서 부분집합을 만들어 그 원소들을 더하여 S가 되는지 알아보아야한다. 따라서 부분 집합 즉, 모든 조합을 만들어 주어야한다.
▶ 비트 마스크와 재귀를 이용해서 둘 다 풀어보았다.

다음 생각

비트 마스크는 bit의 개수로 다가가기 때문에 공집합을 검사해주지 않았지만 재귀로 풀시에는 카운트 변수를 따로 설정 안해주어서 S의 값으로 0이 들어왔다면 결과를 출력하기전에 -1을 해주었다.

다다음 생각

메모리나 시간 다 비트 마스크가 좋긴 하지만 N의 크기가 최대 20 밖에 안되므로 이 문제에서는 큰 차이는 없었다.

▶ 후에 N의 크기가 큰걸 풀어볼 때 비교를 확실히 해봐야겠다.

방안

1) 조합 만들기를 연습해 보는 좋은 문제였다.

(1) 비트 마스크로 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

package baekjoon.q1000;   import java.util.Scanner;   public class Q1182_Bit {     static int n,s;     static int[] arr;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         s = sc.nextInt();                  // 입력 받기         arr = new int[n];         for(int i=0;i<n;i++)             arr[i] = sc.nextInt();                  // 결과값 초기화         result = 0;         solve();         System.out.println(result);     }          static int result;     private static void solve() {         // 모든 조합을 만들어 주자.         for(int i=0;i<(1<<n);i++) {             // 선택될 개수가 1개 이상이면             if(Integer.bitCount(i)>0) {                 int sum = 0;                 for(int j=0;j<n;j++) {                     // 해당 선택 index 더해주기                     if(((1<<j)&i)>0)                         sum += arr[j];                 }                 if(sum==s) result++;             }         }     } }

(2) 재귀로 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

package baekjoon.q1000;   import java.util.Scanner;   public class Q1182 {     static int n,s;     static int[] arr;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         s = sc.nextInt();                  arr = new int[n];         visited = new int[n];         // 입력 받기         for(int i=0;i<n;i++)             arr[i] = sc.nextInt();                  // 결과값 초기화         result = 0;         solve(0);         // 0일 경우 공집합도 들어가므로 빼주기         if(s==0) result--;         System.out.println(result);     }          static int result;     static int[] visited;     private static void solve(int idx) {         if(idx>=n) {             int tSum=0;             // 선택된 idx들 더해주기             for(int i=0;i<n;i++)                 if(visited[i]==1) tSum+=arr[i];             // 주어진 값과 같다면 +1             if(tSum==s) result++;             return;         }         // 자신 미포함         solve(idx+1);         visited[idx]=1;         // 자신 포함         solve(idx+1);         visited[idx]=0;     } }