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

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

 

 

1. n 입력 받고 n개의 정수 입력받기

2. 덧셈, 뺄셈, 곱셈, 나눗셈 개수 입력받기

3. 연산자 순열 구하고 최소값 최댓값 구하기

 

3번에서 순열을 어떻게 구할지가 관건!

첫번째는 모든 경우를 구하는 브루트 포스를 생각할 수 있는데 만약 N이 11이면, 연산자는 10개로 모든 경우의 수는 10^10이 된다.. 시간복잡도를 생각해봤을 때 개오바텡 

두번째로 생각할 수 있는 건 백트레킹!! 

백트레킹은 모든 경우의 수를 탐색하다 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘으로 안봐도 되는 케이스는 보지 않아 브루트포스보다 더 빨리 조건을 구할 수 있다

 

 

 

첫번째 예제를 참고해서 보자면 다음에 올 연산자를 선택할 때 이전에 나왔던 연산자라면 이전으로 돌아가 계속해서 경우의 수를 탐색한다 여기에서 포인트는 "이전에 나왔던 연산자"이기 때문에 isvisited 배열을 활용해 방문 기록을 확인하고 계속해서 탐색을 진행한다

 

[코드]

#include <iostream>

using namespace std;

int n; // 입력값
int arr[11];
long long min_su = 1e9, max_su = -1e9; // 출력값
char op[10], result[10];
bool isvisited[10] = {false};

void oplist(int k, int p, char o)
{
    for (int i = k; i < p; i++)
    {
        op[i] = o;
    }
}

int oper(char result[10])
{

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

    return sum;
}

void operorder(int x)
{
    // x번째에 올 연산자 구하기
    if (x == n - 1)
    {

        if (oper(result) < min_su)
        {
            min_su = oper(result);
        };

        if (oper(result) > max_su)
        {
            max_su = oper(result);
        }
        // cout << " " << oper(result) << "\n";
        return;
    }

    else
    {
        for (int i = 0; i < n - 1; i++)
        {
            if (!isvisited[i])
            {
                isvisited[i] = true;
                result[x] = op[i];
                operorder(x + 1);
                isvisited[i] = false;
            }
        }
    }
}

int main()
{
    int plus, minus, pro, div;

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

    cin >> plus >> minus >> pro >> div;

    // 연산자 순서대로 배열에 담기
    oplist(0, plus, '+');
    oplist(plus, plus + minus, '-');
    oplist(minus + plus, pro + minus + plus, '*');
    oplist(pro + minus + plus, pro + minus + plus + div, '/');

    operorder(0);

    cout << max_su << "\n"
         << min_su;
}