[algorithm] 백준 - 연산자 끼워넣기

이 문제는 dfs이다.

 

덧셈 뺄셈 곱셈 나눗셈 총 4가지의 연산자로 모든 경우의 수를 따졌을 때 최댓값, 최솟값을 구하는 문제이다.

처음에 순열로 구현했었는데, 같은 경우의 수가 여러개 나올 수 있었다.

덧셈 뺄셈 곱셈 나눗셈 각 1개씩으로 이루어진 것이 아닌 여러개로 이루어져 있기 때문이다.

그렇기 때문에 분기를 4가지로 나누어야 한다는 특징이 있었다.

 

코드는 이렇다.

//연산자 끼워넣기
#include <vector>
#include <iostream>
using namespace std;

int num[12];
int maxNum = -9876543210;
int minNum = 9876543210;
void permutation(int index, int size, int plusCount, int minusCount, int multipleCount, int divideCount, int sum){
   if(index == size){
        maxNum = max(maxNum, sum);
        minNum = min(minNum, sum);
        return;
    }
        if(plusCount != 0) permutation(index + 1, size, plusCount - 1,minusCount, multipleCount, divideCount, sum + num[index + 1]);
        if(minusCount != 0) permutation(index + 1, size, plusCount,minusCount - 1, multipleCount, divideCount, sum - num[index + 1]);
        if(multipleCount != 0) permutation(index + 1, size, plusCount,minusCount, multipleCount - 1, divideCount, sum * num[index + 1]);
        if(divideCount != 0) permutation(index + 1, size, plusCount,minusCount, multipleCount, divideCount - 1, sum / num[index + 1]);
}
int main(void){
    int numSize,plus,minus,multiple,divide;
    vector<int> realVector;
    cin >> numSize;
    for(int i = 0; i < numSize; i++){
        cin >> num[i];
    }
    cin >> plus >> minus >> multiple >> divide;
    permutation(0, numSize - 1,plus, minus, multiple, divide,num[0]);
    cout << maxNum << "\n" << minNum;
}