https://www.acmicpc.net/problem/1182
1. 분류
브루트 포스, 비트마스크
2. 풀이
N개의 원소를 갖는 집합에서 합이 S인 부분집합의 개수를 세는 문제.
부분집합은 2^N개만큼 존재한다.
부분집합을 구하는 방법은 여러 가지가 있겠지만 나는 비트연산을 이용했다.
A, B, C를 갖는 집합의 부분집합을 표로 그려보면 다음과 같다.
정수 |
이진수 |
부분집합 |
0 |
000 |
|
1 |
001 |
A |
2 |
010 |
B |
3 |
011 |
A B |
4 |
100 |
C |
5 |
101 |
A C |
6 |
110 |
B C |
7 |
111 |
A B C |
위 사실만 알면 부분집합을 구하는 건 다 한 것이다.
정수 0부터 2^N - 1까지 반복문, 그 안에 원소의 개수(N)개만큼 도는 반복문.
그리고 반복문 두 개의 인덱스를 AND연산하면 부분집합을 구해낼 수 있다.
3. 소스코드
#include <cstdio> int main() { int n, s, cnt = 0, a[25] = { 0 }; scanf("%d %d", &n, &s); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 1; i < (1 << n); i++) { int sum = 0; for (int j = 0; j < n; j++) { if (i & (1 << j)) sum += a[j]; } if (sum == s) cnt++; } printf("%d\n", cnt); return 0; }
'알고리즘' 카테고리의 다른 글
BOJ [1915] 가장 큰 정사각형 (0) | 2017.09.09 |
---|---|
BOJ [1051] 숫자 정사각형 (0) | 2017.09.01 |
BOJ [9461] 파도반 수열 (0) | 2017.08.15 |
BOJ [11501] 이항 계수 2 (0) | 2017.08.15 |
BOJ [2225] 합분해 (0) | 2017.08.15 |