[알고리즘] 연산자 끼워넣기

구현 방식

• 백트래킹을 이용해서 완전탐색한다.

코드

• 최종 코드는 아래와 같다.

vector<int> numbers;
set<int> result;

void solution(int N, int Addition,int Subtraction,int Multiplication,int Division)
{
    backtrk(1,Addition,Subtraction,Multiplication,Division,numbers[0]);
    int min = INT_MAX, max = INT_MIN;
    for(auto& r : result)
    {
        if(r < min) min = r;
        if(max < r) max = r;
    }
    cout << max << "\n" << min;
}

void backtrk(int idx, int Addition,int Subtraction,int Multiplication,int Division, int tmp)
{
    if(idx == numbers.size())
        result.insert(tmp);
    if(0 < Addition)
        backtrk(idx+1, Addition - 1, Subtraction, Multiplication, Division, tmp + numbers[idx]);
    if(0 < Subtraction)
        backtrk(idx+1, Addition , Subtraction - 1, Multiplication, Division, tmp - numbers[idx]);
    if(0 < Multiplication)
        backtrk(idx+1, Addition, Subtraction, Multiplication -1, Division, tmp * numbers[idx]);
    if(0 < Division)
        backtrk(idx+1, Addition, Subtraction, Multiplication, Division -1, tmp / numbers[idx]);
}