백준 15658 연산자 끼워넣기 (2)

연산자 끼워넣기 문제와 똑같다.

다른 점이 있다면 모든 숫자를 다 사용했을 때 함수를 return 시킨다는 것.

 

각 숫자 사이에 4개의 연산자가 다 들어갈 가능성이 있으므로, 4^(N-1)의 시간복잡도를 갖는다.

N이 최대 11이므로 브루트포스로 풀 수 있는 문제이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<int> ans;
int n;
 
void solve(int idx, int sum, int plus, int minus, int mult, int div, vector<int> num) {
    //모든 숫자를 연산에 다 사용하면 return한다.
    if (idx == n) {
        ans.push_back(sum);
        return;
    }
    //하나를 넣냐 안넣냐가 아니라 4개 중 하나를 넣냐 안넣냐기 때문에 4가지 경우로 나뉜다.
    if (plus != 0) solve(idx + 1, sum + num[idx], plus - 1, minus, mult, div, num);
    if (minus != 0) solve(idx + 1, sum - num[idx], plus, minus - 1, mult, div, num);
    if (mult != 0) solve(idx + 1, sum * num[idx], plus, minus, mult - 1, div, num);
    if (div != 0) solve(idx + 1, sum / num[idx], plus, minus, mult, div - 1, num);
}
 
int main(int argc, char** argv) {
    cin >> n;
 
    vector<int> num(n);
    vector<int> op(4);
 
    for (int i = 0; i < n; i++)cin >> num[i];
    for (int i = 0; i < 4; i++)cin >> op[i];
 
    solve(1, num[0], op[0], op[1], op[2], op[3], num);
 
    auto res = minmax_element(ans.begin(), ans.end());
 
    printf("%d\n%d\n", *res.second, *res.first);
 
    return 0;
}