[백준/BOJ] 백준 16938번 : 캠프 준비

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

16938번: 캠프 준비

 

백트래킹으로 문제를 고르는 상황을 확인하여, 해당 상황이 조건에 만족하는지 확인하는 방법을 통해, 조건에 만족해서 문제를 고르는 경우의 수의 개수를 구했다.

 

코드

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

int n;
vector<int> a;
int l, r, x;
int result = 0;

void Solve(int last_selected, int sum, int high_level, int low_level) {

	//문제를 고르는 조건을 만족했을때
	if (sum >= l && sum <= r && (high_level - low_level) >= x) {
		result++;
	}

	if (last_selected == n - 1) {
		return;
	}

	//last_selected 이후 부터 고르는것 고려
	for (int i = last_selected + 1; i < n; i++) {
		//i번째 문제를 고를때
		Solve(i, sum + a[i], max(high_level, a[i]), min(low_level, a[i]));
	}
}

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

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

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		a.push_back(input);
	}

	Solve(-1, 0, -987654321, 987654321);

	cout << result;

	return 0;
}