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

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

14888번: 연산자 끼워넣기

문제요약

숫자들이 주어지고, 그 사이에 연산자들을 끼워넣는다. 만들 수 있는 모든 식의 결과 값들 중 최대값과 최소값을 구한다.
식의 계산은 연산자 우선순위에 상관없이 앞에서부터 계산한다.

문제 해결

모든 연산자 조합을 체크하는 방법을 사용했다. 각 연산자를 0, 1, 2, 3에 대응하고 연산자들(+,-,*,/) 각각의 개수가 주어졌으므로, 연산자 개수만큼 대응하는 정수를 vector에 넣었다. 그리고 next_permutation을 통해 모든 조합을 탐색했다.

질문 게시판 중에 나와 비슷한 방법을 쓴 질문이 있었는데, 그 사람은 next_permutation을 하기 전, 정렬을 하지 않아서 모든 조합을 탐색하지 못하는 문제가 있었다. 
확실히 next_permutation을 통해 모든 조합을 탐색하려면 정렬을 미리 해야하는데, 나는 정렬을 생각하지 못했다. 하지만 다행히 나의 vector는 이미 정렬된 상태로 만들어졌기 때문에 모든 조합을 탐색할 수 있었다.

코드

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

using namespace std;

int N;

int main(){
    cin >> N;
    vector<int> numbers(N);
    for(int& i : numbers){
        cin >> i;
    }

    vector<int> ops;

    int n;
    for(int opcode=0; opcode<4; opcode++){
        cin >> n;
        for(int j=0; j<n; j++){
            ops.push_back(opcode);
        }
    }

    int max_val = -1000000000;
    int min_val = 1000000000;
    do{
        int result = numbers[0];
        for(int i=0; i<N-1; i++){
            switch(ops[i]){
                case 0:
                {
                    result += numbers[i+1];
                    break;
                }   
                case 1:
                {
                    result -= numbers[i+1];
                    break;
                }
                case 2:
                {
                    result *= numbers[i+1];
                    break;
                }
                case 3:
                {
                    result /= numbers[i+1];
                    break;
                }
            }
        }
        if(result > max_val) max_val = result;
        if(result < min_val) min_val = result;
    }while(next_permutation(ops.begin(), ops.end()));

    cout << max_val << '\n' << min_val;
}