[BOJ] 백준 16938번 캠프 준비 C++

문제

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

16938번: 캠프 준비

풀이

백트래킹으로 문제에 대한 조합을 구해주면 되는데 (문제가 2개일때 ~ 모든 문제를 전부 사용했을때)에 대한 모든 상황에 대해 조합을 돌려주어야 모든 경우의 수를 확인할 수 있다. 조합을 돌리다 조합이 완성되면 check함수를 통해 그 조합이 문제의 조건에 성립하는지 확인해주었고 성립한다면 경우의 수를 증가시켜주었다.

코드

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

using namespace std;

int n, l, r, x;
int result = 0;
vector<int> level;
vector<int> problems;
bool isused[16];

bool check()
{
	int sum = 0;

	for (int i = 0; i < problems.size(); i++)
	{
		sum += problems[i];
	}

	sort(problems.begin(), problems.end());

	if (sum >= l && sum <= r && (problems.back() - problems.front()) >= x)
	{
		return true;
	}
	return false;
}

void func(int k, int cnt, int pivot)
{
	if (k == pivot)
	{
		for (int i = 0; i < level.size(); i++)
		{
			if (isused[i])
			{
				problems.push_back(level[i]);
			}
		}
		if (check())
		{
			result++;
		}
		problems.clear();
		return;
	}

	for (int i = cnt; i < level.size(); i++)
	{
		if (!isused[i])
		{
			isused[i] = true;
			func(k + 1, i + 1, pivot);
			isused[i] = false;
		}
	}
}

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

	cin >> n >> l >> r >> x;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		level.push_back(a);
	}

	for (int i = 2; i < level.size() + 1; i++)
	{
		func(0, 0, i);
		memset(isused, false, sizeof(isused));
	}

	cout << result;
}