[Algorithm] 백준 14888번 연산자 끼워넣기

백준 14888번 연산자 끼워넣기

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

말 그대로 연산자를 끼워넣으면 된다.

특정 위치(pos)에서 남아 있는 연산자를 순차적으로 넣어본 후 최대값과 최소값을 찾으면 됨.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
 
#define ll long long int
 
using namespace std;
int N;
ll val[12];
int expr[4];
int exprCnt;
 
ll maxVal = -1e10;
ll minVal = 1e10;
void dfs(int pos, int cnt, ll result) {
    if (pos == N) {
        if (result > maxVal) maxVal = result;
        if (result < minVal) minVal = result;
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (expr[i] > 0) {
            int resultOrigin = result;
            switch (i) {
            case 0:
                result += val[pos];
                break;
            case 1:
                result -= val[pos];
                break;
            case 2:
                result *= val[pos];
                break;
            case 3:
                result /= val[pos];
                break;
            }
            expr[i] --;
            dfs(pos + 1, cnt - 1, result);
            expr[i] ++;
            result = resultOrigin;
        }
    }
}
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> val[i];
    }
    exprCnt = 0;
    for (int i = 0; i < 4; i++) {
        cin >> expr[i];
        exprCnt += expr[i];
    }
    dfs(1, exprCnt, val[0]);
    cout << maxVal << endl << minVal;
    return 0;
}