[SWEA 4008] 숫자 만들기

출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do

#include <iostream>

#include <algorithm>

using namespace std;

 

#define INF 2e9

 

int N, numMAX, numMIN, tmp, tmp2;

int op[4], arr[12];

 

void dfs(int num, int count)

{

    if (count == N - 1) { numMAX = max(numMAX, tmp); numMIN = min(numMIN, tmp); return; }

 

    for (int i = 0; i < 4; i++)

    {

        if (op[i] > 0)

        {

            if (i == 0) {

                tmp = num + arr[count + 1]; op[i]--;dfs(tmp, count + 1);op[i]++;

            }

            else if (i == 1) {

                tmp = num - arr[count + 1]; op[i]--;dfs(tmp, count + 1);op[i]++;   

            }

            else if (i == 2) {

                tmp = num * arr[count + 1]; op[i]--;dfs(tmp, count + 1);op[i]++;   

            }

            else if (i == 3) {

                tmp = num / arr[count + 1]; op[i]--;dfs(tmp, count + 1);op[i]++;

            }

        }

    }

 

}

 

int main()

{

    int T; int tc = 1;

    cin >> T;

    while (T--)

    {  

        cin >> N; numMAX = -INF; numMIN = INF;

        for (int i = 0;i < 4; i++) cin >> op[i];

        for (int i = 0; i < N; i++) cin >> arr[i];

        dfs(arr[0], 0);

        cout << "#" << tc++ << " " << numMAX-numMIN << endl;

    }

         

    return 0;

}