[C++] 백준 - 14888 : 연산자 끼워넣기

문제 링크

14888번: 연산자 끼워넣기

 

풀이 )

  2개의 vector를 사용했다. 각각 숫자를 저장한 vector a, 연산자를 저장한 vector op이다.

  op에는 +, -, *, /를 의미하는 0, 1, 2, 3를 각 연산자의 수에 맞게 넣었다.

  이후 next_permutation()을 사용하여 op vector안에 있는 연산자의 순서를 바꿔가면서 값을 비교한다.

 

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

using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> op;
    int mini = 1e9;
    int maxi = -1e9;

    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i = 0; i < 4; ++i){
        int numOp;
        cin >> numOp;
        if(!numOp)
            continue;
        for(int j = 0; j < numOp; ++j)
            op.push_back(i);
    }

    do{
        int tmp = a[0];
        for(int i = 0; i < n-1; ++i){
            switch(op[i]){
                case 0:
                    tmp += a[i+1];
                    break;
                case 1:
                    tmp -= a[i+1];
                    break;
                case 2:
                    tmp *= a[i+1];
                    break;
                case 3:
                    tmp /= a[i+1];
            }
        }
        mini = min(tmp, mini);
        maxi = max(tmp, maxi);
    }
    while(next_permutation(op.begin(), op.end()));

    cout << maxi << endl << mini << endl;
}

 

주의)

- 최댓값과 최솟값을 단순 0으로 초기화하면 안된다.  ex ) 최댓값이 음수인 경우 답과 무관하게 0으로 나온다.

- next_permutaion()을 사용한 부분에서 do while문이 아닌 while문을 사용할 경우 처음 연산자 순서는 계산을 안하게 된다.