백준 14888: 연산자 끼워넣기

수열에 연산자를 끼워넣는 문제 수열을 순열로 변화시키면 초깃값인 변화되는 문제가 생기므로 연산자를 각자 0 1 2 3으로 인코딩해주고 이를 디코딩하는 방식으로 한다. 연산자를 순열을 돌린다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int main()
{
    int input;
    cin >> input;
    vector<int> num;
    for (int i = 0; i < input; ++i)
    {
        int x;
        cin >> x;
        num.push_back(x);
    }
    vector<int> cal;
    for (int i = 0; i < 4; ++i)
    {
        int x;
        cin >> x;
        for (int j = 0;j < x; ++j)
            cal.push_back(i);
    }
    int min_val = 1000000050;
    int max_val = -1000000050;
    
    do
    {
        int init_val = num[0];
        for (int i = 0; i < cal.size(); ++i)
        {
            if (cal[i] == 0)
                init_val += num[i + 1];
            if (cal[i] == 1)
                init_val -= num[i + 1];
            if (cal[i] == 2)
                init_val *= num[i + 1];
            if (cal[i] == 3)
                init_val /= num[i + 1];
        }
        min_val = min(init_val, min_val);
        max_val = max(init_val, max_val);
    } while (next_permutation(cal.begin(), cal.end()));
 
    cout << max_val << endl << min_val << endl;
    return 0;
}