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

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

백트래킹으로 모든 경우의 수를 확인했다.

 

선택된 연산자를 used 배열에 저장하고, 연산자를 n - 1개 선택했을 때 나열된 숫자들에 대해서 연산을 진행했다.

그리고 max와 min을 갱신했다.

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[12];
int used[12];
int token[4];
int mn = INT32_MAX, mx =INT32_MIN;

void dfs(int k) {
    if (k == n - 1) {
        int result = arr[0];
        for (int i = 1; i < n; i++) {
            if (used[i - 1] == 0)
                result += arr[i];
            else if (used[i - 1] == 1)
                result -= arr[i];
            else if (used[i - 1] == 2)
                result *= arr[i];
            else if (used[i - 1] == 3)
                result /= arr[i];
        }
        mn = min(mn, result);
        mx = max(mx, result);
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (!token[i]) continue;
        used[k] = i;
        token[i]--;
        dfs(k + 1);
        token[i]++;
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < 4; i++)
        cin >> token[i];
    dfs(0);
    cout << mx << '\n' << mn;
    
    return 0;
}