1208번 : 부분수열의 합2

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int n, t;
	cin >> n >> t;
	int f = n / 2;
	int s = n - n / 2; // n이 홀수 일지 짝수 일지 몰라서 이렇게 놨음

	vector<int> first(f); // 앞부분
	vector<int> second(s); // 뒷부분 

	for (int i = 0; i < f; i++) { // 앞부분 입력 받음
		cin >> first[i];
	}
	for (int i = 0; i < s; i++) { // 뒷부분 입력받음
		cin >> second[i];
	}

	vector<int> f_set; // 앞 부분집합의 합들의 집합
	vector<int> s_set; // 뒷 부붑집합의 합들의 집합


	for (int i = 0; i < (1 << f); i++) { // 비트마스크로 앞부분 집합의 합들의 집합을 얻음
		int index = 0;
		int sum = 0;
		for (int j = 1; j < (1 << f); j <<= 1) {
			if (i&j) {
				sum += first[index];
			}
			index++;
		}
		f_set.push_back(sum);
	}
	for (int i = 0; i < (1 << s); i++) { // 비트 마스크로 뒷 부분 집합의 합들의 집합을 얻음
		int index = 0;
		int sum = 0;
		for (int j = 1; j < (1 << s); j <<= 1) {
			if (i&j) {
				sum += second[index];
			}
			index++;
		}
		s_set.push_back(sum);
	}
	 // 오름 차순 정렬
	sort(f_set.begin(), f_set.end());
	sort(s_set.begin(), s_set.end());
	// 뒷부분 리버스
	reverse(s_set.begin(), s_set.end());


	int F = 0;
	int S = 0;
	int sum = f_set[F] + s_set[S];
	f = f_set.size();
	s = s_set.size();
	long long ans = 0;

	while (F < f&&S < s) {

		if (sum == t) {
			long long f_num = 1;
			long long s_num = 1;
			int f_temp = F;
			int s_temp = S;
			while (F < f) {
				F++;
				if (F >= f) break;
				if (f_set[F] == f_set[f_temp]) {
					f_num++;
				}
				else {
					break;
				}
			}
			while (S < s) {
				S++;
				if (S >= s)break;
				if (s_set[S] == s_set[s_temp]) {
					s_num++;
				}
				else {
					break;
				}
			}
			ans += f_num * s_num;
			if (S < s&&F<f) sum = f_set[F] + s_set[S];
		}
		else if (sum > t) { // 크면 S를 증가
			S++;
			if (S < s) sum = f_set[F] + s_set[S];
		}
		else if (sum < t) { // 작으면 F를 증가
			F++;
			if (F < f) sum = f_set[F] + s_set[S];
		}
	}
	if (t == 0) ans -= 1;
	cout << ans << '\n';
	return 0;
}

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

-->크기가 양수인 부분수열이라서 0(공집합)은 제외한다. 

--> 따라서 맨 밑에 목표(t) 가 0일 경우 ans 에서 1을 빼준 값을 리턴한다.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

---

수정  : 비트마스크로 모든 경우의 수를 구하는 부분이 너무 조잡하여 수정하였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i] ;
    }
    int m = n/2;
    n = n-m;
    vector<int> first(1<<n);
    for (int i=0; i<(1<<n); i++) {
        for (int k=0; k<n; k++) {
            if (i&(1<<k)) {
                first[i] += a[k];
            }
        }
    }
    vector<int> second(1<<m);
    for (int i=0; i<(1<<m); i++) {
        for (int k=0; k<m; k++) {
            if (i&(1<<k)) {
                second[i] += a[k+n];
            }
        }
    }
    sort(first.begin(), first.end());
    sort(second.begin(), second.end());
    reverse(second.begin(), second.end());
    n = (1<<n);
    m = (1<<m);
    int i = 0;
    int j = 0;
    long long ans = 0;
    while (i < n && j < m) {
        if (first[i] + second[j] == s) {
            long long c1 = 1;
            long long c2 = 1;
            i += 1;
            j += 1;
            while (i < n && first[i] == first[i-1]) {
                c1 += 1;
                i += 1;
            }
            while (j < m && second[j] == second[j-1]) {
                c2 += 1;
                j += 1;
            }
            ans += c1*c2;
        } else if (first[i] + second[j] < s) {
            i += 1;
        } else {
            j += 1;
        }
    }
    if (s == 0) ans -= 1;
    cout << ans << '\n';
    return 0;
}

---

 

 for (int i=0; i<(1<<n); i++) { // 모든 경우의 수
         for (int k=0; k<n; k++) { // 경우의 수(선택)  길이 // 즉 이진수 길이
            if (i&(1<<k)) {  // 1을 K 만큼 밀어 줌으로써 오른쪽에서 왼쪽으로 체크
                first[i] += a[k]; // i에서 1인 경우 a[k] 저장
            }
        }
    }