[BOJ 16938] 캠프 준비

16938번: 캠프 준비

 

1. 문제 설명

 

2. 구현 아이디어 1 - 맞았습니다 !!

최근 비트마스킹에 익숙해지고자 비트마스킹 유형 문제들을 모아서 풀고 있다.

비트마스킹을 사용한다는 것을 알면 쉽게 풀 수 있다.

 

 N=4일 때,

0001: 1번 문제를 고름

0010: 2번 문제를 고름

0011: 1, 2번 문제를 고름

0100: 3번 문제를 고름

.

.

.

이런 식으로 경우의 수를 정수로 표현한다.

 

그리고 반복문을 사용하여 AND 연산을 사용해서 만약 i번째 자리(뒤에서 시작하며 0부터 시작)가 1일 경우, 해당 문제를 벡터에 저장해둔다. 그리고 원소들의 합, 최댓값, 최솟값을 구해 주어진 조건에 맞으면 방법의 수를 1 키운다.

 

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321
int n, l, r, x;
int ret;
int problems[15];

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> l >> r >> x;
    for (int i = 0; i < n; ++i) {
        cin >> problems[i];
    }

    for (int i = 1; i < (1<<n); ++i) {
        vector<int> v;
        int sum = 0;
        int mx = 0;
        int mn = INF;

        for (int j = 0; j < 15; ++j) {
            // j번째 자리가 1인 경우
            if (i & (1<<j)) {
                v.push_back(j);
                // 문제 난이도의 합 계산
                sum += problems[j];
                // 가장 어려운, 쉬운 문제 계산
                if (problems[j] > mx) mx = problems[j];
                if (problems[j] < mn) mn = problems[j];
            }
        }
        // 조건을 만족하지 않는다면 continue
        if (v.size() <= 1) continue;
        if (sum < l || sum > r) continue;
        if (mx - mn < x) continue;

        ret ++;
    }

    cout << ret << "\n";

    return 0;
}