[BOJ 14888] 연산자 끼워넣기

N개의 수들이 들어오면 N-1 개의 주어진 +,-,*,/ 연산자로 적절히 배열해 최댓값과 최솟값을 구하는 문제다. 수들의 배열은 바뀌지 않는다.

시간 복잡도는 N-1개의 연산자들을 나열하는 것이므로 (N-1)! 이 되겠다. N의 최댓값이 11이므로 N-1은 10 즉 ,10! = 3628800 이다.

완전탐색을 이용해 풀었다. 주의할 점은 최솟값이 음수가 나올 수 있다는 점이다. 이 점 때문에 몇번이나 틀렸다...

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int N;
int a, b;
void solve(vector <int> &num, int pl, int mi, int mul, int div, int index, int cal) {
    if (index == N) {
        if (a > cal) { a = cal; }
        if (b < cal) { b = cal; }
        return;
    }
 
    if (pl > 0) {
        solve(num, pl - 1, mi, mul, div, index + 1, cal + num[index]);
    }
    if (mi > 0) {
        solve(num, pl, mi-1, mul, div, index + 1, cal - num[index]);
    }
    if (mul > 0) {
        solve(num, pl, mi, mul-1, div, index + 1, cal * num[index]);
    }
    if (div > 0) {    
        solve(num, pl, mi, mul, div - 1, index + 1, cal / num[index]);
    }
}
int main() {
    cin >> N;
    vector <int> num(N);
    for (int i = 0; i < N; i++) {
        cin >> num[i];
    }
    int pl; int mi; int mul; int div;
    cin >> pl >> mi >> mul >> div;
    a = 987654321; b = -987654321;
 
    solve(num, pl, mi, mul, div, 1,num[0]);
 
    cout << b << '\n' << a << '\n';
 
    return 0;
}