14888번-연산자 끼워넣기

문제

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

14888번: 연산자 끼워넣기

---

접근방법

1) 접근 사고

가능한 모든 연산의 경우를 탐색해줘야 하는 문제였습니다. DFS 알고리즘을 통해 모든 경우의 수를 구해주었습니다.

 

2) 시간 복잡도

O(V + E)

 

3) 배운 점

매개변수를 적절하게 사용하면 코드의 라인이 절약될 수 있다는걸 느낀 문제입니다.

 

4) PS

---

정답 코드

//20210904
#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 12;
int arr[MAX];
int op[4];
int n ;
int maxValue = INT_MIN;
int minValue = INT_MAX;
 
int main(void)
{
    fastio;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    for(int i = 0; i < 4; i++)
        cin >> op[i];
 
    //각각의 연산자 갯수가 남아있다면 DFS 탐색을 한다. 
    auto DFS = [&](int plus, int minus, int multiply, int divide, int level, int sum, auto &&DFS) -> void{
        //연산을 다했다면 최대값, 최소값 갱신
        if(level == n){
            maxValue = max(maxValue, sum);
            minValue = min(minValue, sum);
            return ;
        }
 
        if(plus > 0)
            DFS(plus -1, minus, multiply, divide, level + 1, sum + arr[level], DFS);
        if(minus > 0)
            DFS(plus, minus - 1, multiply, divide, level + 1, sum - arr[level], DFS);
        if(multiply > 0)
            DFS(plus, minus, multiply - 1, divide, level + 1, sum * arr[level], DFS);
        if(divide > 0)
            DFS(plus, minus, multiply, divide - 1, level + 1, sum / arr[level], DFS);
    };
 
    DFS(op[0], op[1], op[2], op[3], 1, arr[0], DFS);
    cout << maxValue << "\n";
    cout << minValue << "\n";
    return 0;
}