[BOJ] 1450 - 냅색문제

1. 문제 해석

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

1450번: 냅색문제

문제를 읽고 재귀로 완전탐색하면 되겠다 싶었는데 N 제한이 30 인 것을 보고 고민에 빠졌다. 모든 경우를 확인할 때 최대 2^30번을 확인해야 하기 때문이다. 그래서 알아본 Meet in the Middle 알고리즘을 적용하면 수행시간을 크게 줄일 수 있다. (개념 참고: Meet in the Middle) 

• 최대 C만큼의 무게를 담을 수 있는 가방이 있다.

• N개의 물건이 있을 때 물건을 가방에 넣는 모든 경우의 수를 구해야 한다.

 

 

2. 접근방법

• N개의 물건을 A그룹(0~N/2)과 B그룹(N/2+1~N-1)으로 나눈다.

• A그룹과 B그룹을 완전탐색하여 만들 수 있는 무게를 배열 aSum과 배열 bSum에 각각 저장한다.(각 그룹은 2^N/2번 탐색하면 된다.) 

• 배열 bSum을 내림차순으로 정렬한다. (이분 탐색을 하기 위해)

• aSum[i]에 대하여 aSum[i] + bSum[j] <= C를 만족하는 j를 찾는다. 

 

 

3. 주의할 점

• N<= 30 이기 때문에 그냥 완전탐색한다면 경우의 수가 2^30개 이고, 시간 초과가 발생한다.

• C <= 10^9 이기 때문에 배열을 통한 메모이제이션도 어려워 보인다. 

 

4. 소스코드

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

int N, C, ans, idx, aSize, bSize;
int wt[31], aSum[33000], bSum[33000];

void calcLeft(int i, int sum) {
	if (sum > C) return;
	if (i == N / 2) {
		aSum[aSize++] = sum;
		return;
	}
	calcLeft(i + 1, sum + wt[i]);
	calcLeft(i + 1, sum);
}

void calcRight(int i, int sum) {
	if (sum > C) return;
	if (i == N) {
		bSum[bSize++] = sum;
		return;
	}
	calcRight(i + 1, sum + wt[i]);
	calcRight(i + 1, sum);
}

void binarySearch(int st, int ed, long long val) {
	if (st > ed) return;
	int mid = (st + ed) / 2;

	if (bSum[mid] + val <= C) {
		idx = mid;
		binarySearch(mid + 1, ed, val);
	}
	else return binarySearch(st, mid - 1, val);
}

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

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

	calcLeft(0, 0);
	calcRight(N / 2, 0);
	sort(bSum + 0, bSum + bSize);

	ans = 0;
	for (int i = 0; i < aSize; i++) {
		idx = -1;
		binarySearch(0, bSize - 1, aSum[i]);
		ans += (idx + 1);
	}
	cout << ans << '\n';

	return 0;
}