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

1. 문제

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

 

2. 알고리즘 분류

• 이분 탐색
• 중간에서 만나기

 

3. 소스 코드

#include <iostream>
#include <map>
#define MAX_N 40

using namespace std;

int N, S;
int arr[MAX_N];
map<int, int> sum2cnt;
long long cnt;

// 오른쪽 부분수열의 모든 경우의 수 계산
void rightSeq(int mid, int sum) {
	// 수열의 끝까지 도달했을 경우,
	if (mid == N) {
		sum2cnt[sum]++;	// 부분수열의 합을 저장
		return;
	}

	rightSeq(mid + 1, sum + arr[mid]);	// 해당 index의 수열의 값을 더했을 경우,
	rightSeq(mid + 1, sum);				// 해당 index의 수열의 값을 더하지 않았을 경우,
}

void leftSeq(int start, int sum) {
	// 수열의 반까지 도달했을 경우,
	if (start == N / 2) {
		cnt += sum2cnt[S - sum];	// 왼쪽 부분수열의 합 + 오른쪽 부분수열의 합 = S인 경우의 수 더하기
		return;
	}

	leftSeq(start + 1, sum + arr[start]);	// 해당 index의 수열의 값을 더했을 경우,
	leftSeq(start + 1, sum);				// 해당 index의 수열의 값을 더하지 않았을 경우,
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 정수의 개수, S : 부분수열의 합
	cin >> N >> S;

	// 수열 입력
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	rightSeq(N / 2, 0);	// 1. 우선 중간 기준 오른쪽 부분수열의 합의 모든 경우의 수 계산
	leftSeq(0, 0);		// 2. 왼쪽 부분수열의 합을 계산하면서, 왼쪽 부분수열의 합 + 오른쪽 부분수열의 합 = S인 경우의 수 모두 더하기

	if (S == 0) cout << cnt - 1;	// S가 0인 경우, 왼쪽 수열, 오른쪽 수열이 모두 선택되지 않았을 경우(둘 다 공집합일 경우)를 제외하기 위해 1을 빼기
	else cout << cnt;

	return 0;
}

 

4. 유용한 알고리즘

 1) 이분 탐색

1. O(logN) 시간 복잡도로 해당 배열에서 특정 값을 찾는 알고리즘

https://uigwonblog.tistory.com/86

[알고리즘] 이진 탐색(이분 탐색, Binary Search)