1182 : 부분집합의 합

풀이

완전탐색!

dfs로 짜도 되고

n이 작으니까 비트마스킹 해도 된다.

코드

#include <stdio.h>

int n, s, ans, a[21];

int main() {
	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];
		ans += (s == sum);
	}
	printf("%d", ans);
	return 0;
}
#include <stdio.h>

int n, s, a[22];

int f(int now, int sum) {
	if (now == n) return sum == s;
	return f(now + 1, sum) + f(now + 1, sum + a[now]);
}

int main() {
	scanf("%d %d", &n, &s);
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	printf("%d", f(0, 0) + (!s ? -1 : 0));
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-01-09 18:30

Read more posts by this author