[C++] 수식 만들기 - DFS

// 85 수식 만들기 

#include <vector>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

int n = 3;
vector<int> arr = {5, 3, 8};
vector<int> cal = {1,0,1,0}; // 0: +, 1: -, 2: x, 3: /
// 연산을 했을때 최댓값과 최솟값 리턴하기

int max_ = -10000000;
int min_ = 10000000;

void DFS(int L, int total, vector<int> ch){
    if (L == n - 1){
        if (max_ < total){
            max_ = total;
        }
        if (min_ > total){
            min_ = total;
        }
        return;
    }
    for(int i = 0; i < 4; i++){
        if (ch[i] > 0){
            ch[i] -= 1;
            if (i == 0){
                DFS(L+1, total + arr[L+1],ch);
            }
            else if(i == 1){
                DFS(L+1, total - arr[L+1],ch);
            }
            else if(i == 2){
                DFS(L+1, total * arr[L+1],ch);
            }
            else if(i == 3){
                DFS(L+1, total / arr[L+1],ch);
            }
            ch[i] += 1;
        }
    }
}
int main(){

    DFS(0,arr[0],cal);
    cout << max_ << endl;
    cout << min_ << endl;


    return 0;
}