백준 14888 연산자 끼어넣기(c++)

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

14888번: 연산자 끼워넣기

이 문제는 풀 수 있는 방법이 매우 많습니다. 백트래킹도 가능하고, 순열로도 풀 수 있습니다. 저는 순열로 풀었는데 C++에 next_permutaion 내장 함수를 이용하면 구현 방식이 간단하고, 무엇보다 가독성이 좋기 때문입니다.

그리고 모든 연산자의 최대 개수가 10! / (3! * 3! * 2! * 2!) = 2520가지입니다. 이러한 이유 때문에 모든 경우의 수를 조사하는 브루트 포스 문제(완전 탐색)라고도 볼 수 있습니다.

벡터 b에 연산자를 담습니다( +(0), -(1), *(2), /(3)), 그리고 가능한 모든 a, b의 연산을 적용시켜 줘서 최댓값과 최솟값을 출력해 주면 됩니다.

<코드>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 연산의 최대 경우의 수 10! / 3! * 3! * 2! * 2! = 2520, 왜냐하면 중복순열이기 때문이다.(겹치는 경우 동일하게 처리)
int calc(vector<int> &a, vector<int> &b)
{
    int n = a.size();
    int ans = a[0];
    for (int i = 1; i < n; i++)
    {
        if (b[i - 1] == 0)
        {
            ans += a[i];
        }
        else if (b[i - 1] == 1)
        {
            ans -= a[i];
        }
        else if (b[i - 1] == 2)
        {
            ans *= a[i];
        }
        else if (b[i - 1] == 3)
        {
            ans /= a[i];
        }
    }
    return ans;
}
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    // 모든 수 입력 받기
    vector<int> b;
    for (int i = 0; i < 4; i++)
    {
        int cnt;
        cin >> cnt;
        for (int k = 0; k < cnt; k++)
        {
            b.push_back(i);
        }
    }
    // +(0), -(1), X(2), %(3)
    sort(b.begin(), b.end());
    vector<int> result;
    do
    {
        int temp = calc(a, b);
        result.push_back(temp);
    } while (next_permutation(b.begin(), b.end()));

    auto ans = minmax_element(result.begin(), result.end());
    cout << *ans.second << '\n';
    cout << *ans.first << '\n';
    return 0;
}