[백준] 연산자 끼워넣기 No. 14888

• 문제 링크

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

• 문제 해설 및 삽질 내용

모든 경우의 수를 살펴보면서 최대값과 최소값을 확인하면 된다.

연산자 우선순위를 고려하지 않고, 무조건 앞에서 부터 연산을 해야 하기에 dfs로 문제를 해결한다.

• 소스코드

#include <iostream>
#define DBG 0
using namespace std;

long long input[11];
int operator_arr[4];
int used_operator[4];
int N;
long long final_max, final_min;
void DFS(int step, long long ret){
    long long tmp ;
   #if DBG
        cout << "DBG step " << step << " ret : " << ret << endl;
#endif
    if(step == N){
        if(final_max < ret)
            final_max = ret;
        if(final_min > ret)
            final_min = ret;
        return ;
    }
    for(int i = 0; i < 4; ++i){
        if(used_operator[i] < operator_arr[i]){
            tmp = ret;
            ++used_operator[i];
            if(i == 0){
                tmp += input[step];
            }else if( i == 1){
                tmp -= input[step];
            }else if( i == 2 ){
                tmp *= input[step];
            }else{
                tmp /= input[step];
            }
            DFS(step + 1, tmp);
            --used_operator[i];
        }
    }
    return ;
}
int main()
{
    final_min = 1000000000;
    final_max = -1000000000;
    #if DBG
    freopen("input.txt", "r", stdin);
    #endif // DBG
    cin >> N;
    for(int i = 0; i < N; ++i){
        cin >> input[i];
    }
    for(int i = 0; i < 4; ++i){
        cin >> operator_arr[i];
        used_operator[i] = 0;
    }
    DFS(1,input[0]);
    cout << final_max << endl;
    cout << final_min << endl;
    return 0;
}