[백준/C,C++] 14888번: 연산자 끼워넣기

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

연산자의 순서를 바꿔가며 가장 큰 값과 작은 값을 출력해주면 되는 문제입니다.

void dfs(int cnt)
{
    if (cnt == n - 1) {
        calc();
    }
    for (int i = 0; i < FOUR; i++) {
        if (operators[i] > 0) {
            operators[i]--;
            stack.push_back(i);
            dfs(cnt + 1);
            operators[i]++;
            stack.pop_back();
        }
    }
}

먼저 dfs 함수입니다. 연산자를 바꿔가며 5개 모두 배열하였을 땐 함수를 통해 식을 계산합니다. 만약 예제 입력 3의 경우 수열은 1 2 3 4 5 6으로 6개고 연산자는 2 1 1 1로 5개입니다. (+)가 2개, (-)가 1개, (×)가 1개, (÷)가 1개 입력된 경우입니다.

그림으로 나타내면 위와 같습니다. 해당 연산자의 개수를 줄여가며 재귀 호출하므로 주어진 연산자 개수보다 더 사용될 일은 없습니다. 처음 연산자의 순서인 +, +, -, ×, ÷ 의 값을 계산한 이후엔 다시 연산자의 개수를 증가시키며 스택에서 제거한 뒤 부모 노드로 되돌아가 연산자를 +, +, -, ÷, × 의 순서로 두고 결괏값을 계산합니다. 모든 경우의 수를 모두 탐색하기 때문에 브루트포스 알고리즘으로도 분류되어 있는 것 같습니다.

void calc()
{
    int res = nums[0];
    for (int i = 0; i < n - 1; i++) {
        if (stack[i] == 0) res += nums[i + 1];
        else if (stack[i] == 1) res -= nums[i + 1];
        else if (stack[i] == 2) res *= nums[i + 1];
        else res /= nums[i + 1];
    }
    if (maximum < res) {
        maximum = res;
    }
    if (minimum > res){
        minimum = res;
    }
}

연산자가 모두 사용된 경우 해당 식의 값을 계산하며 최댓값과 최솟값을 갱신하여 줍니다.

#include<iostream>
#include<vector>

using namespace std;

#define FOUR 4

int n;
vector<int> nums;
int operators[FOUR];
vector<int> stack;
int maximum = -1000000000;
int minimum = +1000000000;

void calc()
{
    int res = nums[0];
    for (int i = 0; i < n - 1; i++) {
        if (stack[i] == 0) res += nums[i + 1];
        else if (stack[i] == 1) res -= nums[i + 1];
        else if (stack[i] == 2) res *= nums[i + 1];
        else res /= nums[i + 1];
    }
    if (maximum < res) {
        maximum = res;
    }
    if (minimum > res){
        minimum = res;
    }
}

void dfs(int cnt)
{
    if (cnt == n - 1) {
        calc();
    }
    for (int i = 0; i < FOUR; i++) {
        if (operators[i] > 0) {
            operators[i]--;
            stack.push_back(i);
            dfs(cnt + 1);
            operators[i]++;
            stack.pop_back();
        }
    }
}

int main(void)
{
    cin >> n;

    for (int i = 0; i < n; i++) {
        int temp; cin >> temp;
        nums.push_back(temp);
    }
    for (int i = 0; i < FOUR; i++) {
        cin >> operators[i];
    }

    dfs(0);

    cout << maximum << endl << minimum;

    return 0;
}