[BOJ / C++] 14888 연산자 끼워넣기 (삼성기출)

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

문제풀이

• 주어진 수의 순서를 바꿀 수 없으므로, 인덱스 0부터 N-1까지 모두 선택하여야 한다.
• 따라서 dfs함수의 레벨을 주어진 수 배열의 인덱스로 따지고, N-1레벨까지 지금까지의 총 합 sum인자와 함께 재귀호출하며 백트래킹한다.
• 이때 가장 맨 앞의 숫자는 연산자와 관계없이 총 합에 언제든지 들어가있으므로, 첫 호출 형태는 다음과 같다.
  dfs(1, numbers[0]) : 1레벨 (1인덱스) 숫자를 어떤 연산자로 계산할 건지, 지금까지의 총 합은 numbers[0] (제일 맨 앞 숫자)
• dfs 내에서는 +, -, *, / 4가지 연산자 모두로 가지를 뻗어야하고, 이때 연산자마다 개수가 정해져있으므로 남은 연산자 개수가 1개 이상일 때 사용, 재귀호출, 다시 돌려놓기 순으로 작성한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> numbers;
int op[4];
int minVal=2147000000, maxVal=-2147000000;

void dfs(int level, int sum){
    if(level==N){
        minVal=min(minVal,sum);
        maxVal=max(maxVal,sum);
        return;
    }

    //4개 부호 모두 가지뻗기
    //+
    if(op[0]>0){
        op[0]--;
        dfs(level+1,sum+numbers[level]);
        op[0]++;
    }
    //-
    if(op[1]>0){
        op[1]--;
        dfs(level+1,sum-numbers[level]);
        op[1]++;
    }
    //*
    if(op[2]>0){
        op[2]--;
        dfs(level+1,sum*numbers[level]);
        op[2]++;
    }
    // /
    if(op[3]>0){
        op[3]--;
        dfs(level+1,sum/numbers[level]);
        op[3]++;
    }
}

int main(){

    cin>>N;
    for(int i=0;i<N;i++){
        int val;
        cin>>val;
        numbers.push_back(val);
    }
    for(int i=0;i<4;i++){
        cin>>op[i];
    }
    dfs(1,numbers[0]); // 처음 숫자는 무조건 들어가고, 1레벨부터 4개 부호 전부 가지를 뻗어봄.
    cout<<maxVal<<"\n"<<minVal<<"\n";
}