[ 백준 16938 ] 캠프 준비 (C++)

백준의 캠프준비(16938) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 조합으로 구현해보았다.

   조합을 구하는 방법을 잘 모른다면 아래의 글을 읽고 오도록 하자.

   [ 조합 구현하기 바로가기(Click) ]

   조합을 구현한 이유는 { 1, 2 } 번 문제를 뽑나, { 2, 1} 번 문제를 뽑나 결과가 같기 때문에 순열이 아닌

   조합으로 구현해보았다.

   조합을 구현하면서 뽑은 조합의 갯수가 2개 이상이라면, 문제의 조건과 비교해주고 맞다면 정답의 갯수를 ++ 하는 식으로

   구현해 보았다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 15
using namespace std;
 
int N, L, R, X, Answer;
int Problem_Level[MAX];
bool Select[MAX];
 
vector<int> V;
 
void Input()
{
    cin >> N >> L >> R >> X;
    for (int i = 0; i < N; i++)
    {
        cin >> Problem_Level[i];
    }
}
 
void DFS(int Idx, int Cnt, int Level_Sum)
{
    if (Cnt >= 2)
    {
        int Min = 987654321;
        int Max = -987654321;
        int Sum = 0;
 
        for (int i = 0; i < V.size(); i++)
        {
            Sum = Sum + Problem_Level[V[i]];
            if (Problem_Level[V[i]] < Min) Min = Problem_Level[V[i]];
            if (Problem_Level[V[i]] > Max) Max = Problem_Level[V[i]];
        }
 
        if (L <= Sum && Sum <= R && Max - Min >= X) Answer++;
    }
 
    for (int i = Idx; i < N; i++)
    {
        if (Select[i] == true) continue;
        
        if (Level_Sum + Problem_Level[i] <= R)
        {
            Select[i] = true;
            V.push_back(i);
            DFS(i, Cnt + 1, Level_Sum + Problem_Level[i]);
            V.pop_back();
            Select[i] = false;
        }        
    }
}
 
void Solution()
{
    DFS(0, 0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}