이번 문제는 백트레킹을 통해 해결하였다.

• DFS의 인자를 현재 인덱스+1,누적된 결과값, +갯수, -갯수, *갯수, /갯수로 정의한다.
• 모든 경우를 전부 비교해야 하므로 각 연산자의 갯수가 0보다 크다면 그 연산을 진행한다.
• DFS의 첫번째 인자, 즉 현재 인덱스+1에 해당하는 값이 n과 같아지면 하나의 식을 완성한 것이므로 대소비교를 통해 maxi, mini를 업데이트 시켜준다.

처음에는 DFS의 인자를 현재 인덱스+1,누적된 결과값로만 넣고 진행하였는데, 이렇게 구현하게 되면 연산자들에 대한 모든 경우를 구할 수 없었다. 그래서 연산자의 수를 직접 변경하는 것이 아닌, DFS함수 내에서만 임의 변경하여 모든 경우를 탐색할 수 있게 하였다.

그리고 maxi와 mini의 초기값을 설정할 때, result가 음수인 경우를 생각하지 못하고, mini는 10억으로 설정하였지만, maxi를 0으로 설정하여 오답처리 되었다. 이를 maxi=-10억, mini=10억하여 해결하였다.

Code

#include <iostream>
#include <algorithm>
#define MAX 12
using namespace std;

int n;
long long arr[MAX];
int op[4];
long long maxi=-1000000000;
long long mini=1000000000;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    for(int i=0; i<4; i++){
        cin>>op[i];
    }
}

void DFS(int cur, long long result, int plus, int minus, int mul, int div){
    if(cur==n){
        if(maxi<result)
            maxi=result;
        if(mini>result)
            mini=result;
        return;
    }
    if(plus>0){
        DFS(cur+1, result+arr[cur], plus-1, minus, mul, div);
    }
    if(minus>0){
        DFS(cur+1, result-arr[cur], plus, minus-1, mul, div);
    }
    if(mul>0){
        DFS(cur+1, result*arr[cur], plus, minus, mul-1, div);
    }
    if(div>0){
        if(result==0)
            DFS(cur+1, 0, plus, minus, mul, div-1);
        else
            DFS(cur+1, result/arr[cur], plus, minus, mul, div-1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    DFS(1, arr[0], op[0], op[1], op[2], op[3]);
    cout<<maxi<<endl<<mini<<endl;
    return 0;
}