[14888번] 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

문제에서 주어진 수열의 순서는 변경이 없고, 주어진 연산자들의 순서만 바꿀 수 있습니다.

또한 연산사 우선순위를 따지지 않고 앞에서부터 계산하는데, 그때 가능한 최대값과 최소값을 구하는 문제입니다.

 

연산자를 +, -, *, / 의 순서대로 배열에 저장합니다.

배열에 저장할 때는 덧셈부터 차례대로 0, 1, 2, 3이 되며, 덧셈이 두개라면 0을 두번 저장하게 됩니다.

그리고 이렇게 만들어진 연산자 배열을 다음 순열 함수를 이용하여 연산자 순서의 모든 경우의 수를 만들어낼 수 있습니다.

연산자의 최대 개수가 10을 넘어가지 않는다는 문제의 조건이 있으므로 최대 \(10!\)의 경우의 수를 다 계산해도 성능에 문제가 없습니다.

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int calc (vector<int> &a, vector<int> &op) {
    int ans = a[0];
    for (int i = 0; i < op.size(); i++) {
        if (op[i] == 0) { //더하기
            ans += a[i + 1];
        }else if(op[i] == 1) { //빼기
            ans -= a[i + 1];
        }else if(op[i] == 2) { //곱하기
            ans *= a[i + 1];
        }else { //나누기
            ans /= a[i + 1];
        }
    }
    return ans;
}
int main () {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> op;
    for (int i = 0; i < 4; i++) { //+, -, *, / 연산자 순서대로 0,1,2,3 
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            op.push_back(i); //연산자 번호를 개수만큼 저장
        }
    }
    int max = -1e9; //-10억
    int min = 1e9; //10억
    do {
        int t = calc(a, op);
        if (max < t) max = t;
        if (min > t) min = t;
    } while (next_permutation(op.begin(), op.end()));
    
    cout << max << '\n';
    cout << min << '\n';
    
    return 0;
}

 

[결과]

3 //input
3 4 5 //input
1 0 1 0 //input
35
17