[백준] 16938 캠프 준비

✔️ 문제 링크

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

16938번: 캠프 준비

---

✔️ 문제 이해

◾ N개의 문제가 있고, 각 문제에 대한 난이도는 정수로 수치화 되어있다. i번째 문제의 난이도는 Ai 이다.

◾ 주어진 N개의 문제에서 캠프에서 사용할 문제를 구해야한다.

◾ 문제를 고르는 조건은 아래와 같다.

1. 캠프에 사용할 문제는 2문제 이상이어야한다.

2. 고른 문제들의 난이도 합은 L보다 크거나 같고, R보다 작거나 같다.

3. 고른 문제중 가장 어려운 문제 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 한다. 

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

 

---

✔️ 설계

◾ 주어진 문제중 2문제 이상을 골랐을때 조건에 맞는 모든 경우의 수를 모두 찾는 문제이다. 

◾ 문제를 고르거나 고르지 않거나 둘 중 하나이다. 최대 15문제이므로 최대 2^15 경우의 수가 나온다. 

◾ 비트마스킹으로 모든 경우의 수를 간단히 구하는 방법을 선택했다. 

◾ 좀 더 상세한 설명은 주석으로 넣었다.

---

👨🏻‍💻 소스 코드

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

int p[15];
int n, l, r, x;
int ret = 0;

bool check(int bit) {

	int cnt = 0;
	int score = 0;
	int maxScore = 1, minScore = 10000000;

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

		// flag를 활용하여 선택된 문제를 선별한다. 
		int flag = bit & (1 << i); 

		// 1로 표시된 bit는 선택된 문제다. 아래 코드로 출력해서 확인해보자.
		// cout << bitset<16>(flag) << endl;

		if (flag != 0) {  // 선택된 문제라면(bit가 1이라면),
			score += p[i]; // 점수를 더한다.
			maxScore = max(maxScore, p[i]); // 최대 점수 값 갱신.
			minScore = min(minScore, p[i]); // 최소 점수 값 갱신.
			cnt++; // 골라진 문제 수 카운트.
		}

	}

	// 조건에 부합하는 경우라면 true 반환.
	if ((score >= l && score <= r)
		&& abs(maxScore - minScore) >= x
		&& cnt >= 2) {
		return true;
	}
	else
		return false;
}

int main() {

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

	for (int i = 0; i < n; i++) { // 문제 정보 입력.
		cin >> p[i];
	}

	for (int bit = 0; bit < (1 << n); bit++) { // 2^n 까지의 모든 경우의 수를 구해본다.
		if (check(bit)) { // 각 경우가 조건에 만족하는지 체크.
			ret++;
		}
	}

	cout << ret;
	return 0;
}

---

✔️ 문제 회고

◾ 2^n 가지 경우의 수중 조건에 만족하는 모든 경우의 수를 구하는 간단한 문제였다. 

◾ 재귀 또는 비트마스킹으로 풀 수 있다. 나중에 재귀로도 풀어봐야겠다.

◾ 비트마스킹에 더 익숙해질 필요가 있다고 느꼈다.