C++ / 16938 / 캠프 준비 ( 비트마스킹 )

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

문제 요약

알고리즘 캠프를 열려면 많은 준비가 필요합니다. 그 중 가장 중요한 것은 문제입니다. 오늘은 백준이를 도와 알고리즘 캠프에 사용할 문제를 고르려고 합니다.

백준이는 문제를 N개 가지고 있고, 모든 문제의 난이도를 정수로 수치화했습니다. i번째 문제의 난이도는 Ai입니다.

캠프에 사용할 문제는 두 문제 이상이어야 합니다. 문제가 너무 어려우면 학생들이 멘붕에 빠지고, 문제가 너무 쉬우면 학생들이 실망에 빠지게 된다. 따라서, 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 합니다. 또, 다양한 문제를 경험해보기 위해 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 합니다.

캠프에 사용할 문제를 고르는 방법의 수를 구해야합니다.

문제 풀이

1. 필요한 변수와 문제의 난이도 배열을 입력받습니다.

2. 1부터 1<<n 까지 탐색합니다. (1 ~ n 의 각 노드를 선택하거나 선택하지 않거나 하는 모든 경우의 수 )

3. 현재 경우의수에서 유효한 노드들의 난이도 합과 가장 작은값, 큰값을 저장합니다.

4. 난이도가 l 이상 r 이하이고 가장 큰 난이도와 가장 작은 난이도의 차가 x 이상인 경우를 세어줍니다.   

5. 세어준 경우의 개수를 출력합니다.

주의할 점

주의할 점은 딱히 없을듯

코드

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


using namespace std;

int n, l, r, x;
int ret = 0;
vector<int>v;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> l >> r >> x;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}

	// 모든 경우의수
	for (int i = 1; i < (1 << n); i++)
	{

		int mincnt = 1e9;
		int maxcnt = 0;
		int sum = 0;
		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j))
			{
				// 난이도의 합
				sum += v[j];
				// 최저 난이도 문제
				mincnt = min(v[j], mincnt);
				// 최고 난이도 문제
				maxcnt = max(v[j], maxcnt);
			}
		}

		// l 보다 크고 r보다 작은 난이도
		if (l <= sum && sum <= r)
		{
			// 최고 난이도  최소 난이도의 차이가 x 이상
			if ((maxcnt - mincnt) >= x)
			{
				ret++;
			}
		}
	}
	cout << ret;
	return 0;
}

예제 1

3 5 6 1
1 2 3

결과 1

예제 2

4 40 50 10
10 20 30 25

결과 2

예제 3

5 25 35 10
10 10 20 10 20

결과 3