[C++] BJO 14888 : 연산자 끼워넣기

문제

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

 

 

 

풀이

BFS를 활용한 완전탐색으로 풀었다.

 

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int n;
int a[100];
int method[4]; // 0: +, 1:-, 2:*, 3:/
int min_ans = 100000000, max_anx = -100000000;

struct State{
    int cal, idx;
    int m[4];
};

int main()
{
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    for(int i=0; i<4; i++){
        cin >> method[i];
    }
    
    queue<State> q;
    q.push({a[0], 1, {method[0], method[1], method[2], method[3] }});
    
    while(!q.empty()){
        State cur = q.front();
        q.pop();

        if(cur.idx >= n){
            if(cur.cal > max_anx) max_anx = cur.cal;
            if(cur.cal < min_ans) min_ans = cur.cal;
        }
        
        else{
            for(int i=0; i<4; i++){
                if(cur.m[i] > 0){
                    switch(i){
                        case 0 : 
                            q.push({cur.cal + a[cur.idx], cur.idx+1, {cur.m[0]-1,cur.m[1], cur.m[2], cur.m[3]}});
                            break;
                        case 1 :
                            q.push({cur.cal - a[cur.idx], cur.idx+1, {cur.m[0],cur.m[1]-1, cur.m[2], cur.m[3]}});
                            break;
                        case 2 :
                            q.push({cur.cal * a[cur.idx], cur.idx+1, {cur.m[0],cur.m[1], cur.m[2]-1, cur.m[3]}});
                            break;
                        case 3 :
                            int next_cal;
                            if(cur.cal < 0) {
                                next_cal = -(-cur.cal / a[cur.idx]);
                            }
                            else next_cal = cur.cal / a[cur.idx];
                            q.push({next_cal, cur.idx+1, {cur.m[0],cur.m[1], cur.m[2], cur.m[3]-1}});
                            break;
                    }
                }
                
            }
        }
    }
    
    cout << max_anx << "\n";
    cout << min_ans << "\n";

    return 0;
}