[BOJ/백준 14888][C++] 연산자 끼워넣기

문제

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

백준 14888

 

문제 내용

연산에 사용될 수들과 연산자가 주어진다.

연산에 사용되는 수들은 순서를 바꾸지 않고 입력된 순서대로 사용한다.

연산자는 순서를 바꾸어 식을 계산했을 때 가장 큰 결과와 작은 결과를 출력하면 된다.

(단, 연산은 우선순위 관계없이 좌->우로 계산한다.)

 

문제 풀이

백트래킹을 통해 연산자의 순서를 결정하면 된다. 

같은 연산자가 여러번 사용될 수도 있지만, 개수의 제한이 있다는 것을 유념해야 한다.

아래 N과 M(9) 문제와 푸는 방식이 유사하다.

[BOJ/백준 15663][C++] N과 M (9)

 

코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int operators[10]; // 0은 +, 1은 -, 3은 x, 4는 /
bool used[10];

int n;
int arr[11];
int operOrder[10];
vector<long long> results;

long long calcNum() {
    long long result = arr[0];
    for (int i = 0; i < n - 1; i++) {
        if (operOrder[i] == 0) {
            result += arr[i + 1];
        } else if (operOrder[i] == 1) {
            result -= arr[i + 1];
        } else if (operOrder[i] == 2) {
            result *= arr[i + 1];
        } else {
            result /= arr[i + 1];
        }
    }
    return result;
}

void back(int cnt) {
    if (cnt == n - 1) { // 연산자를 다 사용했을 때
        long long num = calcNum();
        results.push_back(num);
        return;
    }

    int dup = -1; //똑같은 연산을 막기 위함
    for (int i = 0; i < n - 1; i++) {
        if (dup != operators[i] && !used[i]) {
            dup = operators[i];
            used[i] = true;
            operOrder[cnt] = operators[i];
            back(cnt + 1);
            used[i] = false;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int tmp = 0, cur = 0;
    for (int i = 0; i < 4; i++) {
        cin >> tmp;
        for (int j = 0; j < tmp; j++) {
            operators[cur] = i;
            cur++;
        }
    }

    back(0);

    sort(results.begin(), results.end());
    cout << results[results.size() - 1] << '\n' << results[0];
}