백준 14888 연산자 끼워넣기 (재귀)

앞에 까지 재귀로 푼 문제들은 하나의 경우를 선택하느냐 선택하지 않느냐 하는 문제였다.

하지만 이번 문제는 연산자 4가지 중 하나를 넣느냐 아니면 넣지 않느냐 하는 문제이기 때문에 경우의 수를 4가지로 나누어서 풀었다.

연산자의 수가 주어진 숫자의 수 보다 1개 적어서 딱 맞기 때문에, 불가능한 경우를 따로 만들어줄 필요가 없다.

 

재귀의 종료 조건은 연산자의 개수를 다 사용하여 0개가 되는 것이다.

minmax_element함수를 사용하는 법을 익숙하게 해야 겠다.

auto 연산자를 사용하는 것을 익혀야 한다.

#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 (plus + minus + mult + div == 0) {
        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;
}