[백준,c++] 14888번 - 연산자 끼워넣기

문제

14888번: 연산자 끼워넣기

 

코드

#include <iostream>
#include <vector>

using namespace std;

int N,add,sub,mul,divd;
int max_v=-1e9-1, min_v = 1e9+1;

void backtrack(int result,int index, vector<int>&num, int add, int sub, int mul, int divd){
    
    if(index==N){
        max_v = max(max_v, result);
        min_v = min(min_v, result);
        return;
    }
    
    if(add>0) backtrack(result+num[index], index+1, num, add-1, sub, mul, divd);
    if(sub>0) backtrack(result-num[index], index+1, num, add, sub-1, mul, divd);
    if(mul>0) backtrack(result*num[index], index+1, num, add, sub, mul-1, divd);
    if(divd>0) backtrack(result/num[index], index+1, num, add, sub, mul, divd-1);
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    vector<int>num(N);
    
    for(int i=0; i<N; i++) cin>>num[i];
    cin>>add>>sub>>mul>>divd;
    backtrack(num[0],1,num,add,sub,mul,divd);
    cout<<max_v<<'\n'<<min_v;
}

 

풀이

모든 연산의 경우를 돌아보며 최댓값과 최솟값을 갱신하는 완전 탐색을 통해 구현했습니다. 처음에 설계만 어떻게 할지 떠올리면 쉬운 문제였는데 요즘 알고리즘을 안 풀다 보니 머리가 굳어서 next_permuation을 통해 순열로 구현해보려다가 안풀려서 피를 본 문제였습니다.😢