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

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

14888번: 연산자 끼워넣기

---

연산자 끼워넣기 문제는 백트래킹을 이용하였습니다.

 

next_permutation()를 이용하여 연산자 수열의 모든 경우의 수를 뽑아내고, 각 수열에 대해 연산식을 계산하면 됩니다.

주의할 점은 next_permutation()을 호출하기 전에 대상 배열이 정렬되어 있어야 합니다. 또한 100 이하의 정수가 최대 11개 주어지며, 곱셈 연산이 있으므로, Int형이 아닌 long long형을 사용해야합니다.

 

아래는 전체 코드입니다. 

 

#include <bits/stdc++.h>
using namespace std;

long long num[11];
long long b = LONG_MIN;
long long s = LONG_MAX;

char op[4] = {'+', '-', '*', '/'};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    
    for(int i =0; i < n; i++) cin >> num[i];
    
    vector<char> np;

    for(int i = 0; i < 4; i++){
        int c; cin >> c; 
        // 연산자의 개수만큼 연산자를 벡터에 넣어준다. (ex. 2 1 1 1 -> np = {'+','+','-','*', /'})
        for(int j = 0; j < c; j++) np.push_back(op[i]); 
    }

    sort(np.begin(), np.end()); // next_permutation를 사용하기 위해서는 대상 배열이 정렬되어 있어야 함

    do{
        long long t = num[0];   // 연산식 가장 앞의 정수
        for(int i = 0; i < np.size(); i++){
            switch(np[i]){  // 연산자에 따라 연산 수행
                case '+' : t = t + num [i + 1]; break;  
                case '-' : t = t - num [i + 1]; break;
                case '*' : t = t * num [i + 1]; break;
                case '/' : t = t / num [i + 1]; break;
            }
        }
        b = max(b, t);
        s = min(s, t);
    }while(next_permutation(np.begin(), np.end())); // 각 연산자 수열에 대해 반복
    
    cout << b << "\n" << s;
}