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

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

14888번: 연산자 끼워넣기

 

문제 설명

n개의 수로 이루어진 수열이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 n-1개의 연산자가 주어진다. (+, -, *, /)

수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행한다. n개의 수와 n-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구한다.

N (2 <= N <= 11)

(1 <= Ai <= 100)

해결

간단한 백트래킹 문제이다. 깊이가 n일 때 최댓값, 최솟값을 갱신한다.

수와 수 사이에 들어갈 수 있는 연산자는 총 4개이므로 4번 반복문을 돌며 연산자 배열에 해당 순서 연산자가 남아 있다면 함수를 불러 재귀적으로 들어간다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n;
int MAX = -INF;
int MIN = INF;
vector<int> v;
int oper[4];

void func(int cnt, int num) {
    if (cnt == n) {
        if (num > MAX) MAX = num;
        if (num < MIN) MIN = num;
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (oper[i] <= 0) continue;
        oper[i]--;
        if (i == 0) func(cnt + 1, num + v[cnt]);
        else if (i == 1) func(cnt + 1, num - v[cnt]);
        else if (i == 2) func(cnt + 1, num * v[cnt]);
        else func(cnt + 1, num / v[cnt]);
        oper[i]++;
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    for (int i = 0; i < 4; i++)
        cin >> oper[i];


    func(1, v[0]);
    cout << MAX << "\n" << MIN;
}