BOJ 1450 - 냅색문제

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1851	502	348	29.392%

문제

---

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

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

입력

---

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

출력

---

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

접근

---

Map으로 냅색문제처럼 풀어보려고 했으나 메모리초과가 났다.
질문 게시판을 보니 경우의 수를 반으로 분할해서 푸는 문제였다.

그래서, 15까지의 경우와 그 이후의 경우로 경우의 수를 나누었다.
두 벡터의 합이 C 이하인 경우를 다 더하면 된다.

풀이

---

L과 R 벡터로 경우의 수 배열을 두개 만들었다.
이후 각 DFS 형식으로 solve를 진행했다.

벡터의 값들이 다 채워지면 정렬해준다.
그리고 L 벡터를 순회하면서, R이 C - l 보다 작은 원소의 갯수를 찾아주고 더하면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, C, arr[30];
ll ans = 0;
vector<int> L, R;

void leftSolve(int idx, int num)
{
	if (num > C) return;
	if (idx == 15 || idx >= N)
	{
		L.push_back(num);
		return;
	}
	leftSolve(idx + 1, num + arr[idx]);
	leftSolve(idx + 1, num);
}

void rightSolve(int idx, int num)
{
	if (num > C) return;
	if (idx >= N)
	{
		R.push_back(num);
		return;
	}
	rightSolve(idx + 1, num + arr[idx]);
	rightSolve(idx + 1, num);
}

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

	CIN2(N, C);
	FUP(i, 0, N - 1) CIN(arr[i]);
	leftSolve(0, 0);
	rightSolve(15, 0);
	sort(ALL(L));
	sort(ALL(R));
	for (int l : L)
	{
		int r = upper_bound(ALL(R), C - l) - R.begin();
		ans += r;
	}
	COUT(ans);


	return 0;
}