백준 14888번: 연산자 끼워넣기

문제

문제 바로가기> 백준 14888번: 연산자 끼워넣기

풀이

backtracking을 이용해 쉽게 풀 수 있다! 주의해야 할 점은 결과값이 -10억~10억이므로 초기 min_res, max_res 값을 각각 INF와 -INF로 설정해 주어야 한다는 점이다. 처음에 max_res를 0으로 초기화해주어서 틀렸다 😅

#include<iostream>
#include<vector>
#define MAX 12
#define INF 1000000000
using namespace std;

vector<int> v;
int num[MAX], oper[4];
int N, min_res=INF, max_res=-INF;

void input(){
    cin >> N;
    for(int i=0; i<N; i++) cin >> num[i];
    for(int i=0; i<4; i++) cin >> oper[i];
}

void solution(){
    if(v.size()==N-1){
        int idx = 1;
        int res = num[0];
        for(int i=0; i<(int)v.size(); i++){
            if(v[i]==0) res+=num[idx];
            else if(v[i]==1) res-=num[idx];
            else if(v[i]==2) res*=num[idx];
            else if(v[i]==3) res/=num[idx];
            idx++;
        }
        min_res = min(res, min_res);
        max_res = max(res, max_res);
        return ; 
    }
    for(int i=0; i<4; i++){
        if(!oper[i]) continue;
        v.push_back(i); oper[i]--;
        solution();
        v.pop_back(); oper[i]++;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
    cout << max_res << "\n" << min_res;
}