백준, BOJ, 16938번, 캠프 준비 C++ [CPP] ★★

전형적인 백트래킹문제이면서

조건이 많이 달린 문제다.

쉬웠다.

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

int N,L,R,X;

vector<int> level;

//조건 난이도 합 L보다 크거나 같음
// 난이도 합 R보다 작거나 같음
// 난이도 차 X보다 크거나 같음

int ans;

void func(int cnt, int idx, int maxi, int mini, int sum){
    if(cnt == N){
        if(maxi - mini >= X){
            if(sum <= R && sum >= L){
                ans++;                
            }
        }
        return;
    }
    
    //i번째 문제를 포함한 것과 아닌 것
    for(int i = idx; i<N; i++){
        func(cnt + 1, i+1, max(level[i], maxi), min(level[i], mini), sum + level[i]);
        func(cnt + 1, i+1, maxi, mini, sum);
    }
}

int main(){
    cin >> N >> L >> R >> X;
    for(int i = 0; i<N; i++){
        int lev;
        cin >> lev;
        level.push_back(lev);
    }
    func(0,0,0,123456789,0);
    cout << ans << '\n';
    
    
    return 0;
}