[백준 14888] 연산자 끼워넣기, C++

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

14888번: 연산자 끼워넣기

본 문제는 주어진 더하기, 빼기, 곱하기, 나누기를 모두 사용하여 최댓값과 최솟값을 구하는 문제다. 이때 사칙연산은 무시한다. next_permutation을 이용하여 모든 경우를 계산하였다. 이때 최댓값과 최솟값이 int의 범위를 벗어날 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
 
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    int plus, sub, mul, div;
    scanf("%d %d %d %d", &plus, &sub, &mul, &div);
 
    vector<int> u;
    for (int i = 0; i < plus; i++) {
        u.push_back(0);
    }
    for (int i = 0; i < sub; i++) {
        u.push_back(1);
    }
    for (int i = 0; i < mul; i++) {
        u.push_back(2);
    }
    for (int i = 0; i < div; i++) {
        u.push_back(3);
    }
 
    long long Max = -987654321, Min = 987654321;
 
    do {
        long long tmp = v[0];
        for (int i = 0; i < u.size(); i++) {
            if (u[i] == 0) tmp += v[i+1];
            else if (u[i] == 1) tmp -= v[i+1];
            else if (u[i] == 2) tmp *= v[i+1];
            else if (u[i] == 3) tmp /= v[i+1];
        }
        if (Max < tmp) Max = tmp;
        if (Min > tmp) Min = tmp;
    } while (next_permutation(u.begin(), u.end()));
 
    printf("%lld\n", Max);
    printf("%lld\n", Min);
}