[백준 C++] 1208 부분수열의 합 2 - 중간에서만나기

1208번: 부분수열의 합 2

---

 

문제풀이

 

1182번(부분수열의 합) 문제에서 N의 크기만 다른 문제입니다.

N의 크기가 20일 때는 브루트포스 알고리즘을 이용해서 한 번에 풀 수 있지만($2^{20}$번 연산 수행),

이 문제에서는 N의 크기가 40이기 때문에 같은 방법으로 풀면 시간초과가 발생합니다. ($2^{40}$번 연산 수행)

따라서 전체 수열을 반으로 나눠서 왼쪽 부분 수열, 오른쪽 부분 수열의 합을 각각 구해주어 풀어야 합니다.

풀이 과정은 다음과 같습니다.

 

1. 브루트포스 알고리즘을 이용해서 왼쪽 수열의 모든 경우의 부분 수열의 합 계산

2. 해시 맵에 1번 단계에서 구한 각각의 합의 개수를 저장

3. 브루트포스 알고리즘을 이용해서 오른쪽 수열의 모든 경우의 부분 수열의 합(sum) 계산

4. 해시 맵에 저장된 [S - sum]의 개수 만큼 카운트

 

* 주의사항. S가 0일때, 왼쪽 수열에서 공집합을 선택한 경우와 오른쪽 수열에서 공집합을 선택한 경우가 카운팅되므로 마지막에 카운트 -1을 해주어야 합니다. (부분수열의 크기는 양수)

---

코드

#include <iostream>
#include <unordered_map>
using namespace std;

int N, S;
int Seq[40];
unordered_map<int, int> Left;
bool Select[40];

long long Cnt;

void LB(int Idx, int Size)
{
	if (Idx == Size)
	{
		int Sum = 0;
		for (int i = 0; i < Size; ++i)
		{
			if (Select[i])
			{
				Sum += Seq[i];
			}
		}
		++Left[Sum];

		return;
	}

	Select[Idx] = true;
	LB(Idx + 1, Size);
	Select[Idx] = false;
	LB(Idx + 1, Size);
}

void RB(int Idx, int Size)
{
	if (Idx == Size)
	{
		int Sum = 0;
		for (int i = Size / 2; i < Size; ++i)
		{
			if (Select[i])
			{
				Sum += Seq[i];
			}
		}
		Cnt += Left[S - Sum];

		return;
	}

	Select[Idx] = true;
	RB(Idx + 1, Size);
	Select[Idx] = false;
	RB(Idx + 1, Size);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> S;
	
	for (int i = 0; i < N; ++i)
	{
		cin >> Seq[i];
	}

	LB(0, N / 2);
	RB(N / 2, N);

	if (S != 0)
	{
		cout << Cnt;
	}
	else
	{
		cout << Cnt - 1;
	}
}