백준(BOJ) 1182 : 부분수열의 합 (실버2) / 자바(Java) 풀이

문제

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

3줄 요약

1. 정수의 개수 N과 목표 값 S, 그리고 N개의 정수로 이루어진 배열 A를 입력받습니다.
2. 비트마스킹을 활용하여 모든 부분 집합(2^N)에 대해 선택된 정수의 합을 계산하고, 그 합이 목표 값 S와 일치하는 경우의 수를 구합니다.
   • 비트마스킹을 통해 각 정수의 선택 여부를 확인합니다. i & (1 << j)는 i의 이진수 표현에서 j번째 비트가 1인지 확인하는 연산으로, 해당 정수가 부분 집합에 포함되었는지 판단합니다.
   • 선택된 정수들의 합을 계산하고, 그 합이 목표 값 S와 일치하는 경우 answer를 증가시킵니다.
3. 부분 집합의 합이 S와 일치하는 경우의 수를 출력합니다. 이 문제에서는 비트 연산을 활용하여 부분 집합을 효율적으로 생성하고 합을 계산함으로써 문제를 해결할 수 있습니다.

코드

// package boj1182;

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 파일에서 데이터 읽기 (테스트용)
        // System.setIn(new FileInputStream("src/input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 정수의 개수 N과 목표 값 S 입력받기
        String[] tmp = br.readLine().split(" ");
        int N = Integer.parseInt(tmp[0]);
        int S = Integer.parseInt(tmp[1]);
        
        // 정수 배열 A 입력받기
        String[] arr = br.readLine().split(" ");
        int[] A = new int[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = Integer.parseInt(arr[i]);
        }
        
        br.close();
        
        // 부분 집합의 합이 S와 일치하는 경우의 수를 저장할 변수
        int answer = 0;
        
        // 부분 집합의 개수 (2^N)
        int cases = 1 << N;
        
        // 모든 부분 집합에 대해 합 계산
        for (int i = 1; i < cases; i++) {
            int sum = 0;
            
            // 비트마스킹을 활용하여 정수 선택 여부 확인
            for (int j = 0; j < N; j++) {
                if ((i & 1 << j) != 0) { // j번째 정수가 선택되었다면
                    sum += A[j]; // 선택된 정수 더하기
                }
            }
            
            // 부분 집합의 합이 S와 일치하는 경우 answer 증가
            if (sum == S) {
                answer++;
            }
        }
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
    }
}