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

[문제]

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

14888번: 연산자 끼워넣기

[문제풀이]

연산자를 백트래킹을 통해 모든 경우를 파악하자.

사칙연산을 int 값으로 받아온뒤 해당 값만큼 벡터에 저장해주자.(59~76)

visit을 통해 방문을 했는지 아닌지 파악한뒤 방문하지 않았다면 해당 사칙연산을 저장해주자.(42~51)

저장해둔 사칙연산의 연산을 이용해서 마지막 값을 파악한다.(19~32)

max값과 min값 파악.(33~38)

 

[코드]

#include<iostream>
#include<vector>
#include<algorithm>
#define endl "\n"
 
using namespace std;
 
int t;
int Max = -1000000000;
int Min = 1000000000;
int mathmetical[12];
vector<string> answer;
vector<string> arithmetic;
bool visit[102];
 
void backtracking(int n){
    if(n == t-1){
        int total = mathmetical[0];
        for(int i = 0;i<t-1;i++){
            if(answer[i] == "plus"){
                total += mathmetical[i+1];
            }
            else if(answer[i] == "minus"){
                total -= mathmetical[i+1];
            }
            else if(answer[i] == "multiple"){
                total *= mathmetical[i+1];
            }
            else{
                total /= mathmetical[i+1];
            }
        }
        if(total<Min){
            Min = min(Min,total);
        }
        if(total>Max){
            Max = max(Max,total);
        }
        return;
    }
 
    for(int i = 0;i<arithmetic.size();i++){
        if(visit[i] == true){
            continue;
        }
        visit[i] = true;
        answer.push_back(arithmetic[i]);
        backtracking(n+1);
        answer.pop_back();
        visit[i] = false;
    }
}
 
int main(){
    cin>>t;
    for(int i = 0;i<t;i++){
        cin>>mathmetical[i];
    }
    for(int i = 0;i<4;i++){
        int temp;
        cin>>temp;
        for(int j = 0;j<temp;j++){
            if(i == 0){
                arithmetic.push_back("plus");
            }
            else if(i == 1){
                arithmetic.push_back("minus");
            }
            else if(i == 2){
                arithmetic.push_back("multiple");
            }
            else if(i == 3){
                arithmetic.push_back("divide");
            }
        }
    }
 
    backtracking(0);
    cout<<Max<<endl;
    cout<<Min<<endl;
    return 0;
}