[BOJ/비트] 백준 1182 - 부분수열의 합 (Java)

1182 - 부분수열의 합

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

문제

N개의 정수로 이뤄진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수

입력
첫째 줄: 정수의 개수 N, 정수 S (1 <= N <= 20, |S| <= 1,000,000)
둘째 줄: N개의 정수 (|주어지는 정수| <= 100,000)
출력: 합이 S가 되는 부분수열의 개수 

---

풀이

비트

• `1 << N`: 숫자 N개 중 일부를 골라 합이 S가 되는 경우의 수
  -> 부분집합 개수: 2^N개 -> 0 ~ (2^N - 1) 
• `(mask & (1 << i)) != 0`: mask의 i번째 비트가 켜져 있으면 `nums[i]`를 포함
  
  • mask: 부분집합 선택 정보 저장한 숫자 / 비트 하나: 해당 원소 선택했는지 여부
  • ex. mask = 5 = 101 / 1 << i에서 i가 2라면 1 << 2 = 100 
    -> mask & (1 << 2) = 100
  • AND 연산 규칙: 두 비트 모두 1일 때만 1
    -> i번째 비트가 1이면 true = i번째 원소를 포함한다는 의미

int cnt = 0;
for (int mask = 1; mask < (1 << N); mask++) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        if ((mask & (1 << i)) != 0) sum += nums[i];
    }

    if (sum == S) cnt++;
}

 

---

코드

비트

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

public class boj_1182 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        int[] nums = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int cnt = 0;
        for (int mask = 1; mask < (1 << N); mask++) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                if ((mask & (1 << i)) != 0) sum += nums[i];
            }

            if (sum == S) cnt++;
        }

        System.out.println(cnt);
    }
}

 

DFS

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

public class boj_1182 {
    static int N, S;
    static int[] nums;
    static int cnt = 0;

    public static void dfs(int depth, int sum) {
        if (depth == N) {
            if (sum == S) cnt++;
            return;
        }

        dfs(depth + 1, sum + nums[depth]);
        dfs(depth + 1, sum);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        nums = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken());

        dfs(0, 0);
        if (S == 0) cnt--;
        System.out.println(cnt);
    }
}