연산자 끼워넣기 (DFS풀이)

DFS로 풀 수 있는 방법은 여러가지가 있겠지만, 저같은 경우는 각 연산자의 개수를 배열에 저장하고, 각 dfs 단계에서 1개 이상 존재하는 연산자에 대해 1개를 빼고 다음 단계로 진입한 뒤, 현재 단계에 돌아오면 다시 1개를 돌려주는 방식으로 설계를 하였습니다. 결과적으로 완전 탐색이 가능해집니다.

#include <iostream>
using namespace std;

int n, k, no[11], ari[4], ap = 0, ans1 = -2e9, ans2 = 2e9;
void dfs(int now, int idx) {
    if (idx == n-1) {
        ans1 = ans1 < now ? now : ans1;
        ans2 = ans2 > now ? now : ans2;
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (ari[i]) {
            ari[i]--;
            if (i == 0) dfs(now + no[idx + 1], idx + 1);
            if (i == 1) dfs(now - no[idx + 1], idx + 1);
            if (i == 2) dfs(now * no[idx + 1], idx + 1);
            if (i == 3) dfs(now / no[idx + 1], idx + 1);
            ari[i]++;
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> no[i];
    for (int i = 0; i < 4; i++) cin >> ari[i];
    dfs(no[0], 0);
    cout << ans1 << "\n" << ans2;
}