14888 : 연산자 끼워넣기

formula

없음

브루트포스로 전 경우를 다 따져야하는데
방향성이 DFS에 맞춰져있어서 재귀돌리며 모든 케이스 도출

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int operands[12]; // 피연산자
int op[4];        // + - * /
int max_res = -1000000001;
int min_res = 1000000001;

void dfs(int idx, int result) {
    // 탈출 조건
    if (idx == N) {
        max_res = max(max_res, result);
        min_res = min(min_res, result);
        return;
    }

    // 브루트포스
    for (int i = 0; i < 4; i++) {
        if (op[i] > 0) {
            op[i]--; 

            if (i == 0) dfs(idx + 1, result + operands[idx]);
            else if (i == 1) dfs(idx + 1, result - operands[idx]);
            else if (i == 2) dfs(idx + 1, result * operands[idx]);
            else if (i == 3) dfs(idx + 1, result / operands[idx]);

            op[i]++; 
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> operands[i];
    for (int i = 0; i < 4; i++) cin >> op[i];

    dfs(1, operands[0]);

    cout << max_res << '\n' << min_res;
    return 0;
}