[백준] 1182번 : 부분 수열의 합 - JAVA [자바]

가오리·2023년 12월 5일
0
post-thumbnail

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


비트마스크 기법으로 풀 수 있는 문제이다.

비트마스크 기법에 대해서는 이 문제를 보고 오자.

N 은 20보다 작거나 같기 때문에 int 자료형으로 나타낼 수 있다.

우선 원소의 개수가 N 개라면 이 집합의 부분 집합의 수는 2N 제곱개이다.

2N 제곱개는 즉, 1 << N 으로 나타낼 수 있다.

문제에서 공집합(0)은 제외하기 때문에 부분 집합의 갯수는 총 N-1 개이다.

000...0001 일 때부터 1111...111 일 때 까지의 부분 집합을 돌면서 그 부분 집합의 원소들의 합이 S 일때 count++; 을 해준다.

0000...0001 이란 numArr에서 1번째 원소만을 가지고 있는 부분집합을 나타낸다.
000...101 이란 1 번째, 3 번째 원소를 가지고 있는 부분집합을 나타낸다.

그럼 000...101은 뭘까?
바로 5 이다.

즉, 제일 처음 원소 하나만 가지는 집합(0000...0001)부터 모든 원소를 가지는 부분집합(11111...111) 까지 돌면서 부분 집합을 구하는 것이다.

for (int i = 1; i < (1 << N); i++) {
	int sum = 0;
    // 0000...0001 이란
    // numArr에서 1번째 원소만을 가지고 있는 부분집합을 나타낸다.
    // 000...101 이란 1 번째, 3번째 원소를 가지고 있는 부분집합을 나타낸다.
    // 그럼 000...101은 뭘까?
    // 바로 5이다.
    for (int j = 0; j < N; j++) {
    	// numArr에서 1번째 원소를 구한다.
    	if ((i & (1 << j)) != 0) {
    		sum += numArr[j];
		}
	}
    if (sum == S) {
    	count += 1;
	}
}

i = 5 일 때 즉, 000...101 일 때를 보자.
이때 101에 따라 1 번째 3 번째 원소를 부분 집합으로 가진 다는 것의 판별식은 (i & (1 << j)) != 0 이다.
그러므로 numArr[0] 과 numArr[2] 이 더해지고 이 합을 S 와 비교한다.


public class bj1182 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] split = line.split(" ");

        int N = Integer.parseInt(split[0]);
        int S = Integer.parseInt(split[1]);
        int[] numArr = new int[N];
        int count = 0;

        String line1 = br.readLine();
        String[] split1 = line1.split(" ");
        for (int i = 0; i < N; i++) {
            numArr[i] = Integer.parseInt(split1[i]);
        }

        // 원소의 개수가 N 이라면 집합의 부분집합 수는 2의 N승 개이다.
        // 즉, 1<<N개
        // 공집합(0)은 제외하기 때문에 0000...0001부터 시작
        for (int i = 1; i < (1 << N); i++) {
            int sum = 0;
            // 0000...0001 이란
            // numArr에서 1번째 원소만을 가지고 있는 부분집합을 나타낸다.
            // 000...101 이란 1 번째, 3번째 원소를 가지고 있는 부분집합을 나타낸다.
            // 그럼 000...101은 뭘까?
            // 바로 5이다.
            for (int j = 0; j < N; j++) {
                // numArr에서 1번째 원소를 구한다.
                if ((i & (1 << j)) != 0) {
                    sum += numArr[j];
                }
            }
            if (sum == S) {
                count += 1;
            }
        }

        bw.write(count + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

}
profile
가오리의 개발 이야기

0개의 댓글

관련 채용 정보