14888번 연산자 끼워 넣기

 

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

브루트포스를 연습하고 있는데 해당 문제는 DFS로 풀어진걸 참고했다.. 이런 유형은 그냥 DFS가 편한 것 같다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

#define MAX 11

int n; 
int arr[MAX];
int maxCount = INT_MIN;
int minCount = INT_MAX;
void  getCalculate(int index, int number, int add, int sub, int mul, int div)
{
    if (index == n)
    {
        maxCount = max(maxCount, number);
        minCount = min(minCount, number);
    }
    else
    {
        if (add > 0) getCalculate(index + 1, number + arr[index], add - 1, sub, mul, div);
        if (sub > 0) getCalculate(index + 1, number - arr[index], add , sub-1, mul, div);
        if (mul > 0) getCalculate(index + 1, number * arr[index], add , sub, mul-1, div);
        if (div > 0) getCalculate(index + 1, number / arr[index], add , sub, mul, div-1);
    }
}

int main() {

    int plus, minus, div, mul;
    cin >> n;


    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num; 
        arr[i] = num; 
    }

    cin >> plus >> minus >> mul >> div;

    getCalculate(1, arr[0], plus, minus, mul, div);
    cout << maxCount << endl;
    cout << minCount << endl;
      

    return 0;
}