[BOJ/백준][Gold4] 16938 : 캠프 준비 (C++)

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

16938번: 캠프 준비

 

[난이도] Gold4
[유형] 브루트포스

[풀이]
문제를 선택할 수 있는 모든 경우에 대해서 문제에 주어진 조언이 만족되는지를 확인하면 된다.
완전탐색은 비트마스크를 이용해서 구현하였다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16938.cpp

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,L,R,X,a[15],ans;
int main(){
    scanf("%d%d%d%d",&N,&L,&R,&X);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    for(int i=1;i<(1<<N);i++){
        int ml=2e9,mr=0,sum=0,cnt=0;
        for(int j=0;j<N;j++){
            if((i&(1<<j))>0){
                mr=max(mr,a[j]);
                ml=min(ml,a[j]);
                sum+=a[j];
                cnt++;
            }
        }
        if(cnt>=2 && sum<=R&&sum>=L&&mr-ml>=X) ans++;
    }
    printf("%d",ans);
}