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

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

C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n,num;
int arr[12];
vector<int> op;
vector<int> final;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // 수의 개수, 수, +,-,x,/
    // 만들 수 있는 식의 최댓값, 최솟값 ㅊ ㅜㄹ력
    // 연산자 우선  순위 무시하고 앞에서부터 진행

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 4가지 연산자를 각자 위치에 넣는다.

    for(int i = 0; i < 4; i++) {
        cin >> num;
        for(int j = 0; j < num; j++) {
            op.push_back(i);
            // + : 0개, - : 0개, x : 1개, / : 0개
            // 이거를 가지고 모든 경우의 수 구해야하니까 함수 사용
        }
    }

    // 3 4 5가 있고 + : 1개, x : 1개 있을 때 + x : 35 , x + : 17
    // 숫자는 3개, 연산자는 4개
    do {
        int total = arr[0];
        for(int i = 0; i < op.size(); i++) {
            if(op[i] == 0) {
                total += arr[i+1];
            }
            if(op[i] == 1) {
                total -= arr[i+1];
            }
            if(op[i] == 2) {
                total *= arr[i+1];
            }
            if(op[i] == 3) {
                total /= arr[i+1];
            }
        }
        final.push_back(total);
    }while(next_permutation(op.begin(),op.end()));

    sort(final.begin(), final.end());

    cout << final.back() << "\n" << final.front();
}

문제풀이

• 4가지 연산자를 구분해서 어딘가에 담아야한다고 생각했다. 이 연산자를 가지고 순열을 구해야되는데 그러기 위해서는(STL 사용) 한 곳에 있어야하기 때문에. 여러 가지 방법을 고민해봤는데, 각 + - x / 를 i = 0 , 1, 2, 3으로 구분해서 vector 담는 아이디어가 생각났다. 그렇게 되면 op 벡터안에 모든 연산자가 들어가고 STL을 사용하면 이 연산자에 대한 모든 조합을 구할 수 있게 된다. 그리고 0,1,2,3에 따라 연산해준다. 그런 다음 결과값을 의미하는 벡터와 모든 값을 넣어주고 do-while문이 끝난 다음 정렬해준 뒤 최솟값과 최댓값을 출력해준다.

Comment

• 연산자를 어떻게 한 곳에 넣을지에 대해 오래 고민한 것 같다. 으음 STL을 쓸 것이다 생각하고 그 틀에 맞춰서 문제를 풀긴 했는데 이게 정확한 방법인지는 모르겠다...,.,.