[C/C++] 백준 - 16938번 : 캠프 준비

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

16938번: 캠프 준비

이 문제도 백트래킹으로 완전 탐색을 하는 문제이다.

개인적으로 전에 풀었던 문제가 더 까다로웠던 것 같은데 이 문제가 난이도는 더 높게 등록되어있다.

 

이 문제는 조건이 구간으로 나누어져 있어서 정렬을 먼저 한 후 몇 개를 최대로 뽑을 수 있는지 먼저 구해주었다.

만약 입력되는 난이도의 개수가 15개인데, 사실상 조건에 만족하는 개수는 2개 뿐이라면 나머지는 필요없는 연산이기 때문이다. 그래서 가장 먼저 범위에 만족하는 최대 개수를 구해주었다.

그리고 그 후는 똑같이 백트래킹 -> 완전탐색으로 구한 후 최종적으로 조건에 만족하는지만 확인해주면 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define INF 987654321
#define Mod 10007
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, L, R, X, Cnt;
int score[16];
bool visited[16];
vector<int> v;

void func(int Sum, int depth, int start, int total) {
	if (depth == Sum) {
		if (L <= total && total <= R) {
			sort(v.begin(), v.end());
			if (X <= abs(v.front() - v.back())) {
				Cnt++;
			}
		}
		return;
	}

	for (int i = start; i <= N; i++) {
		if (!visited[i]) {
			visited[i] = true;
			v.push_back(score[i]);

			func(Sum, depth + 1, i + 1, total + score[i]);

			visited[i] = false;
			v.pop_back();
		}
	}
}

int main() {
	cin >> N >> L >> R >> X;
	for (int i = 1; i <= N; i++) cin >> score[i];
	sort(score, score + N + 1);

	int Area = 2;
	bool isCan = false;
	while (1) {
		int tot = 0;
		for (int i = 1; i <= Area; i++) {
			tot += score[i];
		}
		if (tot <= R) {
			isCan = true;
			Area++;
		}
		else {
			Area--;
			break;
		}

		if (Area == N + 1) {
			Area--;
			break;
		}
	}

	if (!isCan) cout << 0 << endl;
	else {
		for (int i = 2; i <= Area; i++) {
			for (int j = 1; j <= N; j++) {
				if (!visited[j]) {
					visited[j] = true;
					v.push_back(score[j]);

					func(i, 1, j, score[j]);

					visited[j] = false;
					v.pop_back();
				}
			}
		}
	}
	cout << Cnt << endl;

	return 0;
}