[BOJ 16938 // C++] 캠프 준비

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16938번 문제인 캠프 준비이다.

문제는 아래 링크를 확인하자.

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

16938번: 캠프 준비

N이 최대 15까지인 점을 관찰하자.

 

모든 문제를 고르는 경우의 수가 2^15가지이므로, 모든 경우를 직접 살피는 것으로 문제를 해결할 수 있다.

 

고른 문제가 2문제 이상이어야 한다는 점, 고른 문제들의 난이도 합의 범위가 L 이상 R 이하여야 한다는 점, 가장 어려운 문제와 가장 쉬운 문제의 난이도 차가 X 이상이어야 한다는 점을 하나하나 잘 구현해주자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, L, R, X;
int diff[15];
int ans = 0;

void func(int i, int total, int mn, int mx, int cnt) {
	if (i == N) {
		if (cnt > 1 && L <= total && total <= R && mx - mn >= X) ans++;
		return;
	}
	func(i + 1, total, mn, mx, cnt);
	func(i + 1, total + diff[i], min(mn, diff[i]), max(mx, diff[i]), cnt + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> L >> R >> X;
	for (int i = 0; i < N; i++) cin >> diff[i];

	func(0, 0, 1000000007, -1000000007, 0);

	cout << ans;
}