[Algorithm] Baekjoon 14888번 : 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

int minAnswer = 0;
int maxAnswer = 0;
int n;
int arr[11];
int opCount[11];
 
vector<int> nums;
vector<int> op;
bool isFirst = true;
 
int calc(int a, int b, int op)
{
    switch (op)
    {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return a * b;
    case 3: return a / b;
    }
}
 
void DFS(int index)
{
    if (nums.size() == n)
    {
        int result = calc(nums[0], nums[1], op[0]);
 
        for (int i = 1; i < op.size(); ++i)
        {
            int nextNum = nums[i + 1];
 
            result = calc(result, nextNum, op[i]);
        }
 
        if (isFirst)
        {
            minAnswer = maxAnswer = result;
            isFirst = false;
        }
        else
        {
            maxAnswer = max(maxAnswer, result);
            minAnswer = min(minAnswer, result);
        }
 
        return;
    }
 
    for (int i = 0; i < 4; ++i)
    {
        if (opCount[i] == 0) continue; // 명령어없으면 넘기기
        opCount[i] -= 1;
        op.push_back(i);
        nums.push_back(arr[index + 1]);
 
        DFS(index + 1);
 
        nums.pop_back();
        op.pop_back();
        opCount[i] += 1;
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    
    for (int i = 0; i < 4; ++i)
    {
        cin >> opCount[i];
    }
 
    nums.push_back(arr[0]);
    DFS(0);
 
    cout << maxAnswer << endl;
    cout << minAnswer;
}

경우의 수 뽑는 완전탐색? 느낌의 문제이다.

숫자와 명령어가 주어지는데, 명령어는 순서가 없고 숫자는 순서가 있다.

그렇기 때문에 명령어 기준으로 DFS를 돌리면서 숫자와 명령어를 뽑아서 각각 n개, n-1개 모일때마다 모은걸로 계산을 해서 최소값,최대값을 업데이트 해주면 된다.