[BOJ] 연산자 끼워넣기 15658 C++ 풀이

문제

n과 m

접근방법

구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, m;
int cntPlus, cntMin, cntMul, cntDiv;
vector<int> a;
int Max, Min;

void dfs(int plus, int mult, int min, int div, int idx, int res)
{
    if(idx == a.size())
    {
        if(res > Max) Max = res;
        if(res < Min) Min = res;
        return;
    }

    if(plus < cntPlus) dfs(plus + 1, mult, min, div, idx + 1, res + a[idx]);
    if(mult < cntMul) dfs(plus, mult + 1, min, div, idx + 1, res * a[idx]);
    if(min < cntMin) dfs(plus, mult, min + 1, div, idx + 1, res - a[idx]);
    if(div < cntDiv) dfs(plus, mult, min, div + 1, idx + 1, res / a[idx]);
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0);
    int num;
    Max = -1234567;
    Min = 987654321;

    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>num;
        a.push_back(num);
    }

    cin>>cntPlus>>cntMin>>cntMul>>cntDiv;

    dfs(0, 0, 0, 0, 1, a[0]);
    cout<<Max<<'\n';
    cout<<Min<<'\n';
    return 0;
}