BOJ 1182 : 부분 수열의 합

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/1182

 

 

비트 연산을 이용해 집합을 나타낼 수 있고, 각 집합을 다 더할수도 있다.

set = 1 << N;
for (int i = 1; i < set; i++)
{
	sum = 0;
	for (int k = 0; k < N; k++)
		if (i & (1 << k)) sum += A[k];

	if (sum == S) ans++;
}

 

먼저 N이 5인 집합이라고 가정하자. 그러면 set = 1 << 5 = 32가 된다.

이때, int i = 1; i < set이 의미하는 것은 무엇일까?

 

1부터 31까지 bit로 나타내면 아래와 같다.

 

00001 → 0번 원소 하나만 선택

00010 → 1번 원소 하나만 선택

00011 → 0번 원소, 1번 원소 선택

00100 

00101

00110

...

11110

11111 → 모든 원소 선택

 

최소 1개의 원소는 선택해야하므로 i = 1부터 시작하였다.

 

즉, 1부터 1 << N 까지 for문을 도는 것은, 집합에서 원소를 선택한 경우의 수가 된다.

따라서 for k를 이용해 실제 원소가 있는 경우에만 값을 더해주고 더한 값이 S인지 counting 하면 된다.

전체 코드는 아래를 참고하자.

#include <stdio.h>

int N, S;
int A[50];

int main()
{ 
	int set, sum, ans;

	scanf("%d %d", &N, &S);

	for (int i = 0; i < N;i++) scanf("%d", &A[i]);

	ans = 0;
	set = 1 << N;
	for (int i = 1; i < set; i++)
	{
		sum = 0;
		for (int k = 0; k < N; k++)
			if (i & (1 << k)) sum += A[k];

		if (sum == S) ans++;
	}

	printf("%d\n", ans);

	return 0;
}