반응형
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <iostream> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; int arr[21]; int n, s, sum, ans = 0; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> s; rep(i, n) cin >> arr[i]; int mask = 1; while (mask < (1 << n)) { sum = 0; for (int i = 0;i < n;i++) sum += arr[i] * ((mask >> i) & 1); if (sum == s) ans++; mask++; } cout << ans; } | cs |
반응형