[백준 1208 C++] 부분 수열의 합 2

백준 1208번 부분 수열의 합 2 문제 링크 

https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

문제 풀이 

백준 1208번 부분 수열의 합2문제는 백준 1182번 부분 수열의 합 방식대로 문제를 풀면 시간 초과가 난다. 

그 이유는 정수의 개수가 20에서 40으로 늘어났을 뿐만 아니라 시간 2초에서 1초로 바뀌었기 때문이다. 

 

그렇기에, 1208번 같은 경우에는 부분 수열의 합 계산을 나눠서 진행해주어야 한다. 

즉, 1182번에서 진행했던 것을 2번 진행하는 셈인 것이다. 

 

이렇게 2개로 나누었을 때 발생한 경우를 생각해보면, 아래와 같이 경우를 나눌 수 있을 것이다.

1. 집합 A에서 부분 수열의 합이 존재하는 경우

2. 집합 B에서 부분 수열의 합이 존재하는 경우 

3. 집합 A에서 구한 합 + 집합 B에서 구한 합 = 부분 수열의 합인 경우 

 

1,2의 경우에는 1182번에서 했던 것과 동일하게 (0 ~ N/2-1), (N/2 ~ N)으로 나눠서 진행해주면 된다. 

그리고, 3번의 경우에는 1,2 과정에서 나오는 합들을 각각 A,B 벡터에 저장한 후, 두 개의 합이 부분 수열의 합이 되는지 확인하기 위해 S - A[i]를 한 후, 벡터 B에 이 값(S - A[i]) 이 몇 개 존재하는지 찾아주면 된다. 

 

이 문제의 핵심은 작업을 반으로 나눠서 풀어주는 것이었다. 

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#define MAX 41
	using namespace std;
	int N, S ;
	int arr[MAX] ;
	vector<int> A, B ;
	long long int result = 0;
	void num_of_subsetA(int sum, int k) {
	if ( k >= N / 2) {
	return ;
	}
	sum += arr[k] ;
	if ( sum == S ) result++ ;
	A.push_back(sum) ;
	num_of_subsetA(sum - arr[k], k + 1) ;
	num_of_subsetA(sum, k + 1);
	}
	void num_of_subsetB(int sum, int k) {
	if ( k >= N ) {
	return ;
	}
	sum += arr[k] ;
	if ( sum == S ) result++ ;
	B.push_back(sum) ;
	num_of_subsetB(sum - arr[k], k + 1) ;
	num_of_subsetB(sum, k + 1);
	}
	void subsetA_subsetB() {
	sort(A.begin(), A.end()) ;
	sort(B.begin(), B.end()) ;
	// (S - 집합 A에서 나온 합)이 집합 B에 있는 경우 갯수 만큼 더해줌
	for (int i = 0 ; i < A.size(); i++) {
	int BS = S - A[i] ;
	int low = lower_bound(B.begin(), B.end(), BS) - B.begin() ;
	int high = upper_bound(B.begin(), B.end(), BS) - B.begin() ;
	result += (high - low) ;
	}
	}
	void Input() {
	cin >> N >> S ;
	for (int i = 0 ; i < N ; i++) {
	cin >> arr[i] ;
	}
	}
	int main(void) {
	ios::sync_with_stdio(false) ;
	cin.tie(0) ;
	Input();
	// 집합 A에서 S가 나올 경우
	num_of_subsetA(0, 0) ;
	// 집합 B에서 S가 나올 경우
	num_of_subsetB(0, N/2) ;
	// 집합 A + 집합 B에서 S가 나올 경우
	subsetA_subsetB() ;
	cout << result << '\n';
	return 0 ;
	}

view raw 1208.cpp hosted with ❤ by GitHub