4008 숫자 만들기

숫자가 고정이고 연산자 위치만 바꾸면 되므로,

연산자의 갯수가 0이 아닐때를 기준으로 백트래킹 해주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int t, n, max_res,min_res;
int oper[4];
int a[12];
 
void dfs(int v, int num) {
    
    if (v == n) {
        max_res = max(max_res, num);
        min_res = min(min_res, num);
    }
    else {
        if (oper[0] != 0) {
            oper[0]--;
            dfs(v + 1, num + a[v]);
            oper[0]++;
        }
        if(oper[1] != 0) {
            oper[1]--;
            dfs(v + 1, num - a[v]);
            oper[1]++;
        }
        if (oper[2] != 0) {
            oper[2]--;
            dfs(v + 1, num * a[v]);
            oper[2]++;
        }
        if (oper[3] != 0) {
            oper[3]--;
            dfs(v + 1, num / a[v]);
            oper[3]++;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    
    cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cin >> n;
        for (int i = 0; i < 4; i++) {
            cin >> oper[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
 
        max_res = -1e9;
        min_res = 1e9;
        dfs(1, a[0]);
 
        cout << "#" << tc << " " << max_res - min_res << "\n";
    }
}