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

14888번: 연산자 끼워넣기

이번에는 못풀어서 해답을 찾아본 문제 입니다.

수열에 수를 입력받고 연산자의 갯수를 입력받은뒤

연산자 덧셈, 뺄셈, 곱셉, 나눗셈을 이용한 경우의 수중 연산결과 최대값, 최소값을 구하는 문제입니다.

찾아본 문자의 해답은 재귀를 통한 연산 설계 입니다.

 

천천히 보면서 이해하는데 집중해보려고 합니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);

using namespace std;
int N;
int operands[11]; // 수열 
int operators[4]; // 연산자의 개수
int mymin = 1000000001;
int mymax = -1000000001;

void getanswer(int result, int idx)
{
    if (idx == N)
    {
        if (result > mymax)
            mymax = result;
        if (result < mymin)
            mymin = result;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        if (operators[i] > 0)
        {
            operators[i]--; // 연산자 하나 사용했으므로 1개 줄여줌
            if (i == 0)
                getanswer(result + operands[idx], idx + 1);
            else if (i == 1)
                getanswer(result - operands[idx], idx + 1);
            else if (i == 2)
                getanswer(result * operands[idx], idx + 1);
            else
                getanswer(result / operands[idx], idx + 1);
            operators[i]++; // 다른 연산자를 사용할 것이므로 아까 줄였던 연산자 개수 늘려줌
        }
    }
    return;
}

int main()
{
    fastio;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> operands[i];
    for (int i = 0; i < 4; i++)
        cin >> operators[i];
    getanswer(operands[0], 1);
    cout << mymax << '\n';
    cout << mymin;
    return 0;
}