백준 14888번: 연산자 끼워넣기 (C++)

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

두가지를 생각해주면 된다.

1. + + - - * 이런 상황처럼 같은 연산자가 중복해서 들어가는 경우를 생각해서 연산자를 뽑아야한다.

순열로 뽑아야하므로 같은 것이 포함된 순열을 구현해주면 된다.

2. 연산자 우선순위가 없기 때문에, 단순히 숫자와 연산자를 분리해서 배열에 담은 뒤에, 하나씩 빼서 계산해주면 된다.

#include<iostream>
#include<vector>
#include<set>
using namespace std;
 
vector<int> oprV; //뽑힐 수 있는 연산자들
vector<int> v; //뽑힌 연산자들 저장
set<vector<int> > st;
int n, num[12], oprCnt[4];
bool isused[12];
 
int calc(int a, int opr, int b) {
    if (opr == 0) return a + b;
    else if (opr == 1) return a - b;
    else if (opr == 2) return a * b;
    else if (opr == 3) return a / b; 
}
void func(int k) {
 
    if (k == n - 1) {
        st.insert(v); //set으로 중복 제거
        return;
    }
    
    for (int i = 0; i < n - 1; i++) {
        if (!isused[i]) {
            v[k] = oprV[i];
            isused[i] = true;
            func(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
 
    for (int i = 0; i < 4; i++) {
        cin >> oprCnt[i];
        while (oprCnt[i]--) { // + - * /    0 1 2 3 
            oprV.push_back(i);
            v.push_back(0);
        }
    }
 
    func(0);
 
    //중복 제거 하고 연산자 뽑은 결과
    int mx = -1111111111;
    int mn = 1111111111;
 
    for (set<vector<int> >::iterator itr = st.begin(); itr != st.end(); itr++) {
        vector<int> tmp = *itr;
        int res = num[0];
 
        for (int i = 0; i < tmp.size(); i++) 
            res = calc(res, tmp[i], num[i + 1]);
        
        if (res < mn) mn = res;
        if (res > mx) mx = res;
    }
    cout << mx << '\n' << mn << '\n';
    return 0;
}