백준 14888 C++ - 연산자 끼워넣기

Intro

문제해결 및 소스코드

#include <iostream>

using namespace std;

/*
								<문제해결>
					- N개의 숫자가 주어지면, 연산자는 N-1개가 주어진다.
                    ex)
                        4개의 숫자      - 5 6 7 8
                        3개의 연산자    - +(1개) -(1개) *(0개) /(1개) 
                    - 숫자의 자리는 변하지 않으므로 숫자사이에 연산자를 한번씩 넣어보면서 모든 경우의 수를
                    - 계산하고, 최대 최소값을 출력하면 되는 문제이다.

                    예를들어 5 6 7 8 이라는 숫자가 주어졌을 때
                    먼저, 첫번째 연산자가 들어갈 자리에서 발생하는 경우는 다음 세가지이다.
                    1. 5와 6사이에 + 연산자를 넣었을 때
                    2. 5와 6사이에 - 연산자를 넣었을 때
                    3. 5와 6사이에 / 연산자를 넣었을 때

                    그리고, 각각의 경우에서 또 남은 자리에 남은 연산자들이 들어가는 경우가 생긴다.

                    따라서 이 문제는 재귀호출을 이용하여 해결할 수 있다.
*/

int operands[12];			// .. 최대 11개의 숫자      operands[1]~operands[11] 까지 사용
int operators[5];			// .. 연산자 + - x / 개수   operators[1]~operators[4] 까지 사용(+ - * /순)

int n;						// .. 숫자의 갯수
int maximum = -1000000001;  // .. 최대값을 저장할 변수
int minimum = 1000000001;   // .. 최소값을 저장할 변수

// 연산자가 들어갈 index와 결과값
void Solve(int index, int result)
{
	// 탈출문(최대값 또는 최소값 갱신)
	if (index == n)
	{
		if (result > maximum) maximum = result;
		if (result < minimum) minimum = result;
		return;
	}

	// 해당 index에 4가지 연산자를 모두 대입해보기(+ - * / 순서)
	for (int i = 1;i <= 4;i++)
	{
		// 사용가능한 연산자가 있으면
		if (operators[i] > 0)
		{
			operators[i]--;		// 해당 연산자를 사용했음
			switch (i)
			{
			case 1:
				Solve(index + 1, result + operands[index + 1]);
				break;
			case 2:
				Solve(index + 1, result - operands[index + 1]);
				break;
			case 3:
				Solve(index + 1, result * operands[index + 1]);
				break;
			case 4:
				Solve(index + 1, result / operands[index + 1]);
				break;
			}
			operators[i]++;	    // 다른 경우의수를 위해 갯수 돌려놓기
		}
	}
}

int main()
{
	cin >> n;

	// n개의 숫자 입력
	for (int i = 1;i <= n;i++)
	{
		cin >> operands[i];
	}

	// 연산자 갯수 입력(+ - * / 순서)
	for (int i = 1;i <= 4;i++)
	{
		cin >> operators[i];
	}

    // 첫번째 인덱스부터
	Solve(1, operands[1]);		
	cout << maximum << "\n" << minimum;
}