백준 14888 연산자 끼워넣기

주어지는 숫자의 순서가 바뀌지 않기 때문에 연산자만 순열을 통해 풀면된다.

수의 개수가 최대 11개이므로 연산자의 개수는 최대 10개가 되어 순열로 풀 수 있는 문제이다.

브루트포스로 모든 경우의 수를 만들어 보면서 최댓값과 최솟값을 구한다.

 

algorithm 헤더의 minmax_element함수를 이용한다.

자세한 설명은 코드의 주석으로..

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int main(int argc, char** argv) {
    int n;
    cin >> n;
 
    vector<int> v(n);
    vector<int> oper(4);
    vector<int> res;//모든 결과 값을 담기 쉽도록 배열이 아니라 vector로 선언한다. 모든 결과를 push_back 함수를 통해 넣어준 뒤 minmax_element함수로 답을 추출한다.
 
    for (int i = 0; i < n; i++)cin >> v[i];//수를 입력 받는다.
    for (int i = 0; i < 4; i++) cin >> oper[i];//연산자 개수를 입력받는다.
 
    vector<int> op;
    for (int i = 0; i < 4; i++) {//연산을 위해 각각의 operator를 저장한다.
        while (oper[i]) {
            op.push_back(i);
            oper[i]--;
        }
    }
 
    do {
        int sum = v[0];
        for (int i = 0; i < op.size(); 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];
            }
        }
        res.push_back(sum);//모든 결과 값을 vector에 추가한다.
    } while (next_permutation(op.begin(), op.end()));
 
    auto ans = minmax_element(res.begin(), res.end());//minmax쓰는 법 조심하기. auto는 선언과 동시에 초기화해야 하는 듯.
    printf("%d\n%d\n", *ans.second, *ans.first);//출력할 때 조심. 이름이 minmax니까 min이 first, max가 second이다.
 
    return 0;
}