[삼성SWTest준비]14888번 연산자 끼워넣기

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

삼성SW 기출 문제 한 번에 보기 : https://www.acmicpc.net/workbook/view/1152

삼성 SW 역량평가 기출문제 어떻게 풀지?

먼저, 문제를 보고 역시나 트리 형식을 떠올렸습니다. 

1,2,3,4,5,6 이 있을 때 연산자 우선순위에 상관없는 조건 때문에 1 과 2 사이에 들어 갈 수 있는 연산자만 신경쓰면 되기에 트리를 통해서 모든 경우의 수를 돌아보는 방법을 택했습니다.

/*
14888번 연산자 끼워넣기

브루트 포스 => 트리 형식으로 생각하기
*/
 
#include<iostream>
#include<algorithm>
#define INF 10000000000
using namespace std;
 
int n;
int arr[11];
int cal[4] = { 0 };
int Max = -INF, Min =INF;
int Plus, Minus, Mul, Mod;
 
/*
function 종료 조건
index가 n과 같아 질때
*/
void function(int index, int sum, int plus, int minus, int mul, int mod) {
    if (index == n) {
        Max = max(Max, sum);
        Min = min(Min, sum);
    }
    if (plus > 0)
        function(index + 1, sum + arr[index], plus - 1, minus, mul, mod);
    // puls 면 index가 돌때마다 1씩 감소하고 sum에 더해준다.
    if (minus > 0)
        function(index + 1, sum - arr[index], plus, minus - 1, mul, mod);
    if (mul > 0)
        function(index + 1, sum * arr[index], plus, minus, mul - 1, mod);
    if (mod > 0)
        function(index + 1, sum / arr[index], plus , minus, mul, mod - 1);
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cin >> Plus >> Minus >> Mul >> Mod;
 
    function(1, arr[0], Plus, Minus, Mul, Mod);
 
    cout << Max << " " << Min;
    return 0;
}