풀이
완전탐색!
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이