[BOJ] 16938번 : 캠프 준비(C++)

문제 링크 : 백준 16938번

[문제 접근]

n의 수가 크지 않아서 중복 없는 조합으로 풀었다.
조합을 돌리면서 문제 수가 2문제 이상 선택되었을 때

1. 문제 난이도의 합이 L보다 크거나 같고, R보다 작거나 같고
2. 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같을 때
   ans를 증가시켜주면 된다.

문제 난이도 차이를 구하는 방법으로는 배열을 내림차순으로 정렬 후 조합에 선택되어 있는 것들중(즉, visit[i] = true) 가장 첫 번째로 나오는 것과 가장 마지막에 나오는 것을 선택하면 각각 가장 어려운 문제, 가장 쉬운 문제를 구할 수 있다.

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;
int n,l,r,x,ans=0;
int arr[15];
bool visit[15];

bool cmp(int a, int b) {
    return a>b;
}

void solve(int index, int cnt, int sum) {
    if(cnt>=2) {
        int maxnum, minnum;
        for(int i=0 ; i<n ; i++) {
            if(visit[i] == true) {
                maxnum = arr[i];
                break;
            }
        }
        for(int i=n-1 ; i>=0 ; i--) {
            if(visit[i] == true) {
                minnum = arr[i];
                break;
            }
        }
        if(sum>=l && sum<=r && (maxnum-minnum)>=x) {
            ans++;
        }
    }
    for(int i=index ; i<n ; i++) {
        visit[i] = true;
        solve(i+1, cnt+1, sum+arr[i]);
        visit[i] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> l >> r >> x;
    for(int i=0 ; i<n ; i++) {
        int a;
        cin >> a;
        arr[i] = a;
    }
    
    sort(arr, arr+n, cmp);

    solve(0, 0, 0);
    

    cout << ans << "\n";

    return 0;
}