16938번 캠프 준비

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

기본적인 백트래킹 문제이다.

첫 번째 코드는 내가 직접 푼 코드이고,

두 번째 코드는 정답자 분들 중 짧기도 하고, 깨끗하게 푸신 분이 계셔서

그 분의 코드를 참고하여 다시 구현해본 것이다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, L = 0, R = 0, X = 0, ans = 0;
 
int test_var = 0;
 
vector<int> v;
 
bool use[16] = { false, };
 
bool check(vector<int> vc)
{
    int sum = 0;
 
    for (auto i : vc) sum += i;
 
    int big = *max_element(vc.begin(), vc.end());
    int small = *min_element(vc.begin(), vc.end());
 
    if (sum < L || sum > R || abs(big - small) < X) return false;
 
    return true;
}
 
void simulation(vector<int> vc, int pos)
{
    if (vc.size() >= 2 && check(vc)) ++ans;
    
    if (pos >= v.size()) return;
 
    for (int i = pos; i < v.size(); i++)
        if (!use[i])
        {
            use[i] = true;
            vc.push_back(v.at(i));
 
            simulation(vc, i);
 
            use[i] = false;
            vc.pop_back();
        }
}
 
int main(void)
{
    int score = 0;
 
    scanf("%d %d %d %d", &N, &L, &R, &X);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &score);
 
        v.push_back(score);
    }
 
    vector<int> vc;
 
    simulation(vc, 0);
 
    printf("%d\n", ans);
 
    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, L = 0, R = 0, X = 0, ans = 0;
 
vector<int> v;
 
bool use[16] = { false, };
 
int simulation(int pos)
{
    if (pos >= N)
    {
        int MAX = -1, MIN = 1e9, sum = 0;
 
        for (int i = 0; i < N; i++)
            if (use[i])
            {
                sum += v.at(i);
 
                MAX = max(MAX, v.at(i));
                MIN = min(MIN, v.at(i));
            }
 
        return L <= sum && sum <= R && MAX - MIN >= X;
    }
 
    int ret = 0;
 
    use[pos] = true;
 
    ret = simulation(pos + 1);
 
    use[pos] = false;
 
    return ret + simulation(pos + 1);
}
 
int main(void)
{
    int score = 0;
 
    scanf("%d %d %d %d", &N, &L, &R, &X);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &score);
 
        v.push_back(score);
    }
 
    printf("%d\n", simulation(0));
 
    return 0;
}