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

연산자 끼워넣기

---

아이디어

2
5 6
0 0 1 0 (+-/)
인 경우 1가지 경우
5 6

3
3 4 5
1 0 1 0
인 경우 2가지 경우가 나온다.
3 + 4 5
3 4 + 5

먼저 연산자 배열을 만들어두고, 0번째는 +, 1번째는 -... 이렇게 각 인덱스마다 어떤 연산자가 할당되어있는지 문제에서 이미 정해져 있으므로, 각 인덱스에 해당 연산자가 몇개 사용 가능한지 배열에 저장해준다.

배열에 담긴 첫번째 자리 숫자부터 뒷자리 숫자들과 연산을 해야하는데,
3
3 4 5
1 1 1 0
인 경우 6가지 경우가 생긴다.
3 + 4 - 5
3 + 4 5
3 - 4 5
3 - 4 + 5
3 4 + 5
3 4 - 5

즉 첫번째의 경우 +를 썼으니 op[0]--을 해주어서 Func(1, 7)을 타고 들어갈때 +을 다시 쓰지 못하도록 해준다. 그다음 쓰지 않은 연산자는 [1]인 -가 되기 때문에 Func(2, 2)를 타고 들어갈 수 있다. arr배열의 끝에 도달했기 때문에 식이 완성이된다. 처음에는 ar이 무조건 10억보다 작고 -10억보다 큰 수가 되기 때문에 minValue와 maxValue가 동시에 갱신된다.

재귀함수 Func(2,2)를 빠져나오면 다시 op[1]를 1 증가시켜주고 그 다음 쓰지 않은 연산자를 op배열을 돌면서 찾아본다.

---

제출 코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;

int arr[10] = { 0 };
int op[4] = { 0 };

int num; // 2 이상
int result = 0;

int minValue = 1000000000;
int maxValue = -1000000000;

void Func(int n, int ar)
{
    if (n == num-1)
    {
        if (ar < minValue)
            minValue = ar;
        if (ar > maxValue)
            maxValue = ar;
    }
    else
    {
        for (int i = 0; i < 4; i++)
        {
            if (op[i] > 0)
            {
                op[i]--;

                switch (i)
                {
                case 0: // +
                    Func(n + 1, ar + arr[n + 1]);
                    break;
                case 1:
                    Func(n + 1, ar - arr[n + 1]);
                    break;
                case 2:
                    Func(n + 1, ar * arr[n + 1]);
                    break;
                case 3:
                    Func(n + 1, ar / arr[n + 1]);
                    break;
                }

                op[i]++;
            }
        }
    }
}

int main()
{
    scanf("%d", &num);

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

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

    Func(0, arr[0]);

    printf("%d\n%d", maxValue, minValue);

    return 0;
}