연산자 끼워넣기 14888

문제

접근 방법

아름다울 정도로 조건을 친절하게 작성해준 문제 같다.
문제에서는 Int 범위를 벗어나지 않는다는 것을 알려줬고 연산자 우선순위는 무시되며 앞에서부터 진행된다고 했다.
즉 앞에서부터 차례대로 연산해주면 되는 것이다.
재귀함수를 활용하면 연산의 개수, 여태까지의 값, 인덱스를 저장하여 다음 연산에 활용할 수 있다.

코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<int> nums;
int retMax = INT_MIN, retMin = INT_MAX, N;
void dfs(int idx, int sum, int add, int sub, int multi, int div)
{
    if (idx == N)
    {
        retMax = sum > retMax ? sum : retMax;
        retMin = sum < retMin ? sum : retMin;
        return;
    }
    if (add > 0)
    {
        dfs(idx + 1, sum + nums[idx], add - 1, sub, multi, div);
    }
    if (sub > 0)
    {
        dfs(idx + 1, sum - nums[idx], add, sub - 1, multi, div);
    }
    if (multi > 0)
    {
        dfs(idx + 1, sum * nums[idx], add, sub, multi - 1, div);
    }
    if (div > 0)
    {
        dfs(idx + 1, sum / nums[idx], add, sub, multi, div - 1);
    }
}
int main()
{
    int add, sub, multi, div;
    cin >> N;
    nums = vector<int>(N);
    for (int i = 0; i < N; ++i)
        cin >> nums[i];
    cin >> add >> sub >> multi >> div;
    dfs(1, nums[0], add, sub, multi, div);
    cout << retMax << "\n"
         << retMin;
}

풀이

완전 탐색을 해도 되는 문제인지 판단하고 적용해줄 수 있으면 된다.
중간값도 Int 범위인 것이 확실시됐기에 자료형을 신경 쓸 필요도 없다.