[BruteForce] 백준 14888: 연산자 끼워넣기

14888번: 연산자 끼워넣기 (acmicpc.net)

 

재귀함수 호출을 통한 완전탐색 문제이다. input A_1, A_2, ... , A_n 이 주어졌을 때, 다음과 같은 재귀호출을 통해 답을 구한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxValue = -1000000000;
int minValue = 1000000000;

void recursion(int currentValue, int numIdx, vector<int>&numbers, vector<int>&operators)
{
    if(numIdx>=numbers.size())
    {
        maxValue = currentValue>maxValue?currentValue:maxValue;
        minValue = currentValue<minValue?currentValue:minValue; 
        return;
    }

    for(int i=0;i<4;i++)
    {
        if(operators[i]>0)
        {
            operators[i]--;
            switch(i)
            {
                case 0:
                recursion(currentValue+numbers[numIdx], numIdx+1, numbers, operators);                
                break;
                case 1:
                recursion(currentValue-numbers[numIdx], numIdx+1, numbers, operators);
                break;
                case 2:
                recursion(currentValue*numbers[numIdx], numIdx+1, numbers, operators);
                break;
                case 3:
                recursion(currentValue/numbers[numIdx], numIdx+1, numbers, operators);
                break;
            }
            operators[i]++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    vector<int> numbers;
    vector<int> operators(4);

    cin>>N;
    int input;
    for(int i=0;i<N;i++)
    {
        cin>>input;
        numbers.push_back(input);
    }

    for(int i=0;i<4;i++)
    {
        cin>>input;
        operators[i] = input;
    }

    recursion(numbers[0], 1, numbers, operators);

    cout<<maxValue<<"\n"<<minValue;
}

 

어렵지 않은 방법이지만 operator[i]를 하나 빼서 다음 recursive call에 넘겨주고, 다시 더해서 원상복구해 주는 것을 까먹어서 잠시 고생을 했다.