[백준]1450번 냅색문제 - C++

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

1450번: 냅색문제

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 10^9보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

---

    최대 30가지가 나오므로 물건 하나하나 넣을지 안 넣을지를 결정하면 2^30 이 걸려 시간이 초과가 된다. 그러므로 반을 나누어 왼쪽에서 K 만큼 썼다면 오른쪽에서는 C-K 보다 적게 쓴 경우 알맞은 경우의 수가 된다. 왼쪽과 오른쪽에서 무게와 선택한 개수에 상관없이 선택한 물건들의 무게의 총합을 각각의 벡터에 추가한다. 이제 오른쪽 벡터를 정렬하고 왼쪽 벡터를 순회하며 왼쪽 벡터의 원소가 K 인 경우 오른쪽 원소가 C-K 보다 작은 경우를 추가하면 된다. 이때 벡터가 굉장히 크므로 linear 하게 순회하면 안 되고 upper_bound()를 활용하여 O(logN)의 시간에 K 보다 큰 원소의 위치를 찾아 그 인덱스를 더하면 해결할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N, C;
long long arr[31];
long long cnt=0;

vector<long long> left_sum;
vector<long long> right_sum;

void left(long long s,long long sum) {
	if (s == N/2) {
		left_sum.push_back(sum);
		return;
	}
	left(s + 1, sum);
	left(s + 1, sum + arr[s]);
}
void right(long long s, long long sum) {
	if (s == N) {
		right_sum.push_back(sum);
		return;
	}
	right(s + 1, sum);
	right(s + 1, sum + arr[s]);
}
int main() {
	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	left(0, 0);
	right(N / 2 , 0);
	sort(right_sum.begin(), right_sum.end());

	for (int i = 0; i < left_sum.size(); i++) {
		cnt += upper_bound(right_sum.begin(), right_sum.end(), C - left_sum[i]) - right_sum.begin();
	}
	cout << cnt;
}

---

    처음 문제를 보고 저번 문제와 동일하다고 생각하여 풀었다. 하지만 다른점은 저번에는 key 값이 1'000'000 이 최댓값이었고 이번에는 1'000'000'000이 최대였으며 해당 key 값의 value만 더하는 것이 아니라 주어진 key값보다 작은 value의 값을 모두 더해야 했다. map 에도 upper_bound 가 있지만 iterator 만으로는 map에 key보다 작은 값들이 몇 개가 존재하는지 알기는 어려웠다. 따라서 vector를 이용하여 upper_bound - begin을 활용하여 값을 더해야 시간 안에 들어올 수 있었다. 처음에는 문제를 너무 쉽게 풀 것 같다는 생각을 했지만 저번 문제보다 추가적인 부분이 존재했다. 상당히 아쉬움이 남는 문제였다!