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

 

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

 

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

---

 

 

해결전략

 

비트마스킹 Bitmasking

백트래킹 Backtacking

---

 

 

정답코드

 

#include <iostream>
#include <vector>
using namespace std;
 
int n, l, r, x;  // 문제의 개수, 난이도 합의 최소값, 난이도 합의 최대값, 가장 어려운 문제와 쉬운 문제의 난이도 차이 최소값
vector<int> A;   // 각 문제의 난이도
int answer;      // 조건을 만족하는 경우의 수
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> l >> r >> x;
	A.resize(n);
	for (int i = 0; i < n; i++){
		cin >> A[i];
	}
 
	// 모든 부분집합을 비트마스크를 이용해 탐색
	for (int bitmask = 1; bitmask < (1 << n); bitmask++)
	{
		int sumProblems = 0;    			  // 선택한 문제 난이도의 합
		int easiest = 987654321, hardest = 0; // 선택한 문제들 중 가장 쉬운 문제 난이도, 가장 어려운 문제 난이도
 
		// 비트마스크를 이용해 부분집합 구성
		for (int i = 0; i < n; i++)
		{
			if (bitmask & (1 << i)) // i번째 문제가 선택되었는지 확인
			{
				sumProblems += A[i]; 		  // 선택된 문제 난이도 합산
				easiest = min(easiest, A[i]); // 가장 쉬운 문제 업데이트
				hardest = max(hardest, A[i]); // 가장 어려운 문제 업데이트
			}
		}
 
		// 문제의 난이도 합이 l 이상 r 이하이고, 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이가 x 이상인 경우
		if (l <= sumProblems && sumProblems <= r && (hardest - easiest) >= x){
			answer++; // 조건을 만족하면 경우의 수 증가
		}
	}
 
	cout << answer;
 
	return 0;
}

 

 

---