[14888번] 연산자 끼워넣기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

어느 X사의 문제로 알고있다.(확실하지는 않다.)

이 문제는 BFS로 쉽게 해결할 수 있다.

그 이유로는 문제에서 '연산의 순서는 앞에서부터 차례대로'라고 했기 때문이다.

그렇기에 BFS를 통해 처음 수 -> 끝 수까지 돌며 모든 연산자를 다 파악시키면 된다.

이때 N이 작기에 충분히 가능하다.

이 문제가 만약 더 어려워 진다면, 연산의 순서는 *,/,+,- 처럼 원래 연산의 순서를 지킨다고 했다면 엄청 어렵지 않을까 생각해본다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> pii;
int arr[12];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int plus, minus, mul, div;
    scanf("%d %d %d %d", &plus, &minus, &mul, &div);
 
    queue<pair<pii, pair<pii, pii> > > q;
 
    q.push({{ arr[0], 1 }, { {plus,minus},{mul,div} }});
 
    int maxVal = -1000000010;
    int minVal = 1000000010;
    while (!q.empty())
    {
        int val = q.front().first.first;
        int pos = q.front().first.second;
        int plus = q.front().second.first.first;
        int minus = q.front().second.first.second;
        int mul = q.front().second.second.first;
        int div = q.front().second.second.second;
 
        q.pop();
 
        if (pos == n)
        {
            maxVal = max(maxVal, val);
            minVal = min(minVal, val);
 
            continue;
        }
        if (plus - 1 >= 0)
            q.push({ { val + arr[pos], pos + 1 },{ { plus - 1,minus },{ mul,div } } });
 
        if (minus - 1 >= 0)
            q.push({ { val - arr[pos], pos + 1 },{ { plus, minus - 1 },{ mul,div } } });
 
        if (mul - 1 >= 0)
            q.push({ { val * arr[pos], pos + 1 },{ { plus,minus },{ mul - 1,div } } });
 
        if (div - 1 >= 0)
            q.push({ { val / arr[pos], pos + 1 },{ { plus,minus },{ mul,div - 1 } } });
    }
 
    printf("%d\n", maxVal);
    printf("%d\n", minVal);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>