[백준] 14888 연산자 끼워넣기 c++

 

문제 링크 https://www.acmicpc.net/problem/14888

Key

• +,-,*,/ 4가지의 연산기호를 인자로 받는 DFS함수를 만든다.
• 완전탐색을 하다가 카운트가 n이 되면 최대값과 최솟값을 구해주면 된다.
• 이 유형의 문제들은 보통 이런식으로 모든 연산에 대한 DFS를 탐색하는 식으로 이루어진다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 12;
int n;
int o1, o2, o3, o4;
int arr[MAX];
int maxResult = -100000000;
int minResult = 100000000;
 
void dfs(int plus, int minus, int mult, int divide, int result, int cnt) {
    
    if (cnt == n) {
        maxResult = max(maxResult, result);
        minResult = min(minResult, result);
        return;
    }
    if (plus > 0)
        dfs(plus - 1, minus, mult, divide, result + arr[cnt], cnt + 1);
    if (minus > 0)
        dfs(plus, minus - 1, mult, divide, result - arr[cnt], cnt + 1);
    if (mult > 0)
        dfs(plus, minus, mult - 1, divide, result * arr[cnt], cnt + 1);
    if (divide > 0)
        dfs(plus, minus, mult, divide - 1, result / arr[cnt], cnt + 1);
}
 
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    cin >> o1 >> o2 >> o3 >> o4;
    
    dfs(o1, o2, o3, o4, arr[0], 1);
    cout << maxResult << endl;
    cout << minResult << endl;
}