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

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

1. 문제 이해

첫째 줄에 수의 개수 N, 둘째 줄에는 A1, A2, ..., AN이 주어진다. 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.

 

2. 조건

* 우선순위 무시하고 앞에서 부터 식 계산

* 나눗셈은 몫만 취함

* 음수를 양수로 나눌 때는 양수로 바꾸고 계산 후 음수로 바꾸기

* -10억 ~ 10억 이므로 int 처리 가능

 

3. 풀이

해당 문제는 순열 문제이다.

algorithm 헤더에 있는 next_permutaion 하면 쉽게 풀리는 문제이다.

왜 내 기억 속에는 next_permutation은 정렬해야한다고 생각했는지...

sort 빼니 잘 돌아간다

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
    int n, num;
    vector<int> v, op; //숫자들, 연산자 수
    int minNum = 1000000000, maxNum = -1000000000;

    cin >> n;
    while (n--) {
        cin >> num;
        v.push_back(num);
    }
    for (int i = 0; i < 4; i++) {
        cin >> num;
        for (int j = 0; j < num; j++) {
            op.push_back(i);
        }
    }

    do {
        int sum = v[0];
        for (int i = 0; i < v.size() - 1; i++) {
            switch (op[i]) {
                case 0: // +
                    sum += v[i + 1];
                    break;
                case 1: // -
                    sum -= v[i + 1];
                    break;
                case 2: // *
                    sum *= v[i + 1];
                    break;
                case 3: // /
                    sum /= v[i + 1];
                    break;
            }
        }

        if (sum < minNum) { //최솟값
            minNum = sum;
        }
        if (sum > maxNum) { //최댓값
            maxNum = sum;
        }

    } while (next_permutation(op.begin(), op.end()));

    cout << maxNum << "\n" << minNum;
    return 0;
}