BOJ 14888 - 연산자 끼워넣기(C++)

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

14888번: 연산자 끼워넣기

 

풀이

연산자마다 가능한 수가 정해져있음 -> 해당 연산자 개수와 숫자 개수(N)의 모든 경우의 수 탐색(브루트 포스)

 

1. 연산 순서 백터의 크기가 N-1보다 작으면 현재 사용가능한 연산자중에서 하나를 연산순서에 push,

   연산 순서 백터의 크기가 N-1과 같다면 2로 이동

   * 계산할 수가 N개라면 연산자의 개수는 N-1

2. 해당 연산자 순서에 맞게 끔 입력 숫자를 계산, 계산한 결과로 최소값, 최대값을 갱신

3. 2에서 이용한 연산 순서 백터의 마지막을 pop, 모든 경우의 수에 대해 1 반복

 

#include <iostream>
#include <vector>

using namespace std;

int MIN = 1e9;
int MAX = -1e9;
int N;
int number[12];
int opt_cnt[4];

void calculate(vector<int> order_operation) {
    int res = number[0];
    for (int i = 0; i < order_operation.size();i++ ) {
        if (order_operation[i] == 0) 
            res += number[i + 1];
        
        else if (order_operation[i] == 1) 
            res -= number[i + 1];
        
        else if (order_operation[i] == 2) 
            res *= number[i + 1];
        
        else 
            res /= number[i + 1];     
    }

    MIN = MIN > res ? res : MIN;
    MAX = MAX < res ? res : MAX;
}

void select_operation(vector<int>& order_operation) {
    if (order_operation.size() == N - 1) {
        calculate(order_operation);
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (opt_cnt[i] == 0)continue;
        opt_cnt[i]--;
        order_operation.push_back(i);
        select_operation(order_operation);
        order_operation.pop_back();
        opt_cnt[i]++;
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> number[i];
    }
    for (int i = 0; i < 4; i++) {
        cin >> opt_cnt[i];
    }

    vector<int> order_operation;
    select_operation(order_operation);

    cout << MAX << endl << MIN;
    return 0;
}