[백준] 부분수열의 합(1182번) - Java

백준 문제 풀이 : 부분수열의 합(1182번)(Java)

문제

문제 확인하기

---

풀이

n개의 정수들을 원소로 갖는 수열 arr이 있을 때,
arr의 부분 집합의 총 원소의 합이 s인 경우가 몇개인지 구하는 문제이다.

n의 최대값, 그러니까 수열 arr의 최대 길이는 20이므로, 완전 탐색을 이용하여 문제를 해결할 수 있다.

단순히 모든 경우를 고려하면 된다.
n이 4인 수열 {1, 2, 3, 4}가 주어졌다고 가정하자.
이 수열의 부분 집합은 {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 2, 3, 4}가 존재한다.
이 부분 집합들을 하나씩 찾으면서 해당 부분 집합의 모든 원소의 합이 s와 같아지는 경우의 수를 세면 된다.

비트 마스킹을 이용해서 문제를 풀어보았다.

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

public class Main {
    private static int[] arr;
    private static int count = 0;

    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());

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

        for (int i = 0; i < 1 << n; i++) {
            int sum = 0;
            if (Integer.bitCount(i) > 0) {
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) > 0) {
                        sum += arr[j];
                    }
                }
                if (sum == s) {
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}