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

문제

난이도 : 실버 1 백준 14888번 : 연산자 끼워넣기

코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> v;
vector<int> op;

int answer_max = INT_MIN;
int answer_min = INT_MAX;

int main()
{
    cin >> N;
    
    int input;
    for (int i = 0; i < N; i++)
    {
        cin >> input;
        v.push_back(input);
    }

    for (int i = 0; i < 4; i++)
    {
        cin >> input;

        for (int j = 0; j < input; j++)
        {
            op.push_back(i);
        }
    }

    sort(op.begin(), op.end());

    do
    {
        int sum = v[0];

        for (int i = 0; i < op.size(); i++)
        {
            int a = v[i + 1];

            switch (op[i])
            {
            case 0:
                sum = sum + a;
                break;
            case 1:
                sum = sum - a;
                break;
            case 2:
                sum = sum * a;
                break;
            case 3:
                sum = sum / a;
                break;
            }

        }

        if (sum > answer_max)
            answer_max = sum;

        if (sum < answer_min)
            answer_min = sum;

    }while (next_permutation(op.begin(), op.end()));
   
    cout << answer_max << '\n' << answer_min;


    return 0;
}

풀이

완전탐색으로 모든 경우의 수를 골라 값을 구하는 문제
벡터 v에는 피연산자를 담고 op에는 연산자를 담을 것임. 연산자를 담을 때 next_permutation 함수로 모든 순열을 구하기 위해 int형으로 담아주었다. 0은 덧셈, 1은 뺄셈, 2는 곱셈, 3은 나눗셈으로
오름차순으로 정렬해준 뒤 do-while문을 통해 next_permutation 함수를 돌리고 앞에서부터 연산을 해내가며 최솟값, 최댓값을 구하면 되는 문제이다.
강의에서는 재귀함수로 구현했는데 재귀 함수를 쓰는 케이스는 재귀 함수로 풀어보려는 노력을 해야할 것 같다.
아 그리고 아무 생각없이 answer_max를 처음 0으로 초기화해서 값이 음수밖에 없는 경우 최댓값 갱신이 안되어 처음에 틀렸다. 주의하자

결과