[BOJ 14888] 연산자 끼워넣기(C++)

연산자 끼워넣기(Silver 1)

문제

전체 문제 보기

14888번: 연산자 끼워넣기

접근법

이번 문제는 연산자가 삽입될 수 있는 모든 위치를 완전탐색하여 풀 수 있습니다. 연산자는 수와 수 사이에만 삽입될 수 있기 때문에 연산자가 삽입될 수 있는 위치는 N - 1 개이며 N은 최대 11입니다. 그리고 각 연산자는 사용할 수 있는 개수가 한정적입니다. 그래서 모든 경우의 수를 계산하더라도 \(4^{10} = 1,048,576\) 보다 훨씬 적은 경우의 수가 나올 것이기 때문에 모든 경우의 수를 충분히 계산할 수 있습니다.

그리고 모든 수식의 조합하기 위해서는 Bactracking을 활용할 수 있습니다. 각 탐색의 깊이마다 +,-, *, / 연산자 중 사용 가능한 연산자를 하나씩 대입해보며 Bactracking 하여 모든 경우의 수를 계산할 수 있습니다.

전체 구현

#include <stdio.h>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
const int MIN_INF = -1'000'000'001;
const int MAX_INF = 1'000'000'001;
vector<int> arr;
array<int, 4> op;
int maxVal{ MIN_INF };
int minVal{ MAX_INF };
void Backtracking(int sum, int depth)
{
    if (depth == arr.size() - 1)
    {
        maxVal = max(maxVal, sum);
        minVal = min(minVal, sum);
        return;
    }

    for (int i = 0; i < 4; ++i)
    {
        int temp = sum;
        if (op[i] == 0) continue;
        switch(i)
        {
        case 0:
            sum += arr[depth + 1];
            break;
        case 1:
            sum -= arr[depth + 1];
            break;
        case 2:
            sum *= arr[depth + 1];
            break;
        case 3:
            sum /= arr[depth + 1];
            break;
        }
        op[i]--;
        Backtracking(sum, depth + 1);
        op[i]++;
        sum = temp;        
    }
    return;
}
int main()
{
    int N{}; //  N(2 ≤ N ≤ 11)
    scanf("%d ", &N);
    arr.resize(N);

    for (int i = 0; i < N; ++i)
    {
        scanf("%d ", &arr[i]);
    }

    for (int i = 0; i < 4; ++i)
    {
        scanf("%d ", &op[i]);
    }

    Backtracking(arr[0], 0);

    printf("%d\n%d\n", maxVal, minVal);
    return 0;
}