비트마스크 기법으로 풀 수 있는 문제이다.
비트마스크 기법에 대해서는 이 문제를 보고 오자.
N
은 20보다 작거나 같기 때문에 int
자료형으로 나타낼 수 있다.
우선 원소의 개수가 N
개라면 이 집합의 부분 집합의 수는 2
의 N
제곱개이다.
2
의 N
제곱개는 즉, 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();
}
}