Boj 1208) 부분수열의 합 2

문제

백준 1208

설명

부분수열의 합 문제는 시간복잡도가 기하급수적으로 증가하는 브루트포스 방법으로 풀린다. 하지만 이 문제는 범위가 2배 증가하여 기하급수적인 시간복잡도로 인해 TLE 가 난다.

이를 해결할 전략은 의외로 간단하다. 전체 그룹을 반으로 나누고, 각 그룹 내에서 모든 경우를 구한 후, 두 그룹을 조합하면 지수함수의 지수부분을 절반으로 줄일 수 있다. 만약 조합의 시간복잡도가 O(\(N^2\)) 보다 작다면 단순 브루트포스보다 이득이다.

이런 배경에서 기하급수적인 시간복잡도를 가진 알고리즘의 사용범위를 대략 2배 증가시키는 테크닉이 바로 MITM(Meet in the Middle) 이다.

시간 복잡도

O(\(2^\mathrm{N/2}\))

코드

int n, s, arr[41];
long long ans;
int chk[8000000];

void Make(int cur, int end, int sum = 0)
{
	if (cur == end)
	{
		chk[sum + 4000000]++;
		return;
	}

	Make(cur + 1, end, sum);
	Make(cur + 1, end, sum + arr[cur]);
}

void Find(int cur, int end, int sum = 0)
{
	if (cur == end)
	{
		ans += chk[s - sum + 4000000];
		return;
	}

	Find(cur + 1, end, sum);
	Find(cur + 1, end, sum + arr[cur]);
}

int main()
{
	cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> arr[i];

	Make(0, n / 2);
	Find(n / 2, n);
	if (s == 0) ans--;
	cout << ans;
}