[Brute Force] 캠프 준비

예제 입력 1

3 5 6 1

1 2 3

예제 출력 1

2

2번, 3번 문제를 고르는 방법, 모든 문제를 고르는 방법이 가능하다.

예제 입력 2

4 40 50 10

10 20 30 25

예제 출력 2

2

난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다.

예제 입력 3

5 25 35 10

10 10 20 10 20

예제 출력 3

6

 

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

16938번: 캠프 준비

 

- N 제한이 15이므로, 15개 중 2개 이상의 수를 뽑아서 해당 조건에 만족하는지 체크하고 만족하면 결과+1하도록 구현하였다.

[ 결과(C++17) ]

#include <stdio.h>

constexpr int MAX_COUNT = 15;

int N, L, R, X;
int problems[MAX_COUNT];
bool selected[MAX_COUNT];

int result = 0;

inline int MIN(int a, int b) { return a > b ? b : a; }
inline int MAX(int a, int b) { return a > b ? a : b; }

void go(int start, int cnt)
{
	if (cnt > 1)
	{
		int minHard = 21'0000'0000;
		int maxHard = -21'0000'0000;
		long long hardSum = 0;

		for (int i = 0; i < N; i++)
		{
			if (selected[i])
			{
				hardSum += problems[i];
				minHard = MIN(minHard, problems[i]);
				maxHard = MAX(maxHard, problems[i]);
			}
		}

		if (hardSum >= L && hardSum <= R && (maxHard - minHard) >= X)
		{
			result++;
		}

		if (cnt == N) return;
	}

	for (int i = start; i < N; i++)
	{
		if (selected[i]) continue;

		selected[i] = true;
		go(i + 1, cnt + 1);
		selected[i] = false;
	}
}



int main(void)
{
	scanf("%d %d %d %d", &N, &L, &R, &X);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &problems[i]);
	}

	go(0, 0);

	printf("%d\n", result);

	return 0;
}