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

문제 링크

14888번: 연산자 끼워넣기

 

풀이

백트래킹문제

1. 먼저 숫자가 담긴 arr와 연산자 oper를 입력받는다.
2. func함수에서 DFS를 한다.
   1. 현재 인덱스인 curIdx가 arr.size()와 같다면 연산이 끝난 것이기 때문에 최댓값과 최솟값을 갱신한 후 return한다.
   2. 연산자를 하나씩 보면서 0보다 큰 경우 연산자를 사용(oper[i] -= 1)하고 재귀호출한다.
   3. 재귀호출시, 현재 인덱스는 +1해주고, 현재까지 연산값 curSum을 갱신해주어 넣는다.
   4. 해당 함수 호출이 끝나면 연산자는 원래대로 돌려놓아야 제대로 작동한다.
3. 최댓값과 최솟값을 출력한다.

 

코드

#include <iostream>
#include <vector>
#define INF 1000000001
using namespace std;

int minAns = INF;
int maxAns = -INF;

void func(vector<int> &arr, int oper[], int curIdx, int curSum)
{
    if (curIdx >= arr.size())
    {
        if (minAns > curSum) minAns = curSum;
        if (maxAns < curSum) maxAns = curSum;
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        if (oper[i] > 0)
        {
            oper[i] -= 1;
            switch (i)
            {
                case 0:
                    func(arr, oper, curIdx + 1, curSum + arr[curIdx]);
                    break;
                case 1:
                    func(arr, oper, curIdx + 1, curSum - arr[curIdx]);
                    break;
                case 2:
                    func(arr, oper, curIdx + 1, curSum*arr[curIdx]);
                    break;
                case 3:
                    func(arr, oper, curIdx + 1, curSum / arr[curIdx]);
                    break;
            }
            oper[i] += 1;
        }
    }
}

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

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

    int oper[4]; // + - * /
    for (int i = 0; i < 4; i++)
    {
        cin >> oper[i];
    }

    func(arr, oper, 1, arr[0]);

    cout << maxAns << '\n' << minAns << '\n';

    return 0;
}