[C++] 수식만들기

📄문제

길이가 N인 자연수로 이루어진 수열이 주어집니다. 수열의 각 항 사이에 끼워넣을 N-1개의 연산자가 주어집니다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있습니다.
수열의 순서는 그대로 유지한 채 각 항사이에 N-1개의 연산자를 적절히 배치하면 다양한 수식이 나옵니다.

예를 들면,
수열이 1 2 3 4 5이고 덧셈(+) 1개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 일 때 만들 수 있는 수식은 많은 경우가 존재한다.

그 중 1+2*3-4/5와 같이 수식을 만들었다면 수식을 계산하는 결과는 연산자 우선순위를 따지지 않고 맨 앞쪽 연산자부터 차례로 계산한다. 수식을 계산한 결과는 1이다.

N길이의 수열과 N-1개의 연산자가 주어지면 만들 수 있는 수식들 중에서 연산한 결과가 최대인것과 최소인것을 출력하는 프로그램을 작성하세요.

 

⬇️ 입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 10)가 주어진다. 둘째 줄에 수열이 주어진다. 수열의 값은
100까지이다. 셋째 줄에는 연산자의 각 개수가 차례대로 덧셈(+) 개수, 뺄셈(-) 개수, 곱셈(×)
개수, 나눗셈(÷) 개수로 주어진다. 연산자의 총 개수는 N-1이다.

3 5 3 8 1 0 1 0

 

⬆️ 출력

첫째 줄에는 최댓값을, 둘째 줄에는 최솟값을 출력한다.

64 23

 

📝 풀이

풀이 1

#include <iostream>

int N, min = INT_MAX, max = INT_MIN;

int numbers[11];

// 연산자 경우의 수 (1~9)
bool ch[10];
int res[10];
int operators[10];

int calc(int a, int b, int operatorId)
{
	switch (operatorId)
	{
	case 1:
		return a + b;
	case 2:
		return a - b;
	case 3:
		return a * b;
	case 4:
		return a / b;
	}
}

void DFS(int level)
{
	// 사용 개수가 R에 도달했다면?
	if (level == N - 1)
	{
		// 최초 1회 계산
		int result = calc(numbers[1], numbers[2], operators[res[1]]);

		// 다음부터는 누적된 값으로 계산
		for (int i = 2; i < N; ++i)
			result = calc(result, numbers[i + 1], operators[res[i]]);

		if (max < result)
			max = result;
		if (min > result)
			min = result;
	}
	else
	{
		for (int i = 1; i <= N - 1; ++i)
		{
			if (!ch[i])
			{
				// 출력 결과는 res[level + 1]에 담기
				res[level + 1] = i;

				// ch[i]번째의 값을 현재 사용중
				ch[i] = true;

				// 개수는 1씩 증가
				DFS(level + 1);

				// ch[i]번째의 값을 현재 사용 해제
				ch[i] = false;
			}
		}
	}
}

int main()
{
	scanf_s("%d", &N);

	for (int i = 1; i <= N; ++i)
	{
		scanf_s("%d", &numbers[i]);
	}

	int plus, minus, multiply, divide;
	scanf_s("%d %d %d %d", &plus, &minus, &multiply, &divide);

	int idx = 0;
	for (int i = 0; i < plus; ++i)
		operators[++idx] = 1;

	for (int i = 0; i < minus; ++i)
		operators[++idx] = 2;

	for (int i = 0; i < multiply; ++i)
		operators[++idx] = 3;

	for (int i = 0; i < divide; ++i)
		operators[++idx] = 4;

	// 0번 인덱스로 시작
	DFS(0);

	printf("%d\n%d", max, min);
}

• [순열구하기]를 응용하여 연산자를 가질 수 있는 경우의수로 모두 뽑아서 계산하는 방법을 이용하여 해결하였습니다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int a[20], op[5], n, maxi = INT_MIN, mini = INT_MAX;

void DFS(int L, int res)
{
	// 모든 수를 사용했다면?
	if (L == n)
	{
		if (res > maxi) maxi = res;
		if (res < mini) mini = res;
	}
	else
	{
		// 각 연산자의 개수를 모두 소모하여 계산을 시도
		if (op[0] > 0)
		{
			op[0]--;
			DFS(L + 1, res + a[L]);
			op[0]++;
		}
		if (op[1] > 0)
		{
			op[1]--;
			DFS(L + 1, res - a[L]);
			op[1]++;
		}
		if (op[2] > 0)
		{
			op[2]--;
			DFS(L + 1, res * a[L]);
			op[2]++;
		}
		if (op[3] > 0)
		{
			op[3]--;
			DFS(L + 1, res / a[L]);
			op[3]++;
		}
	}
}

int main()
{
	int i;
	scanf_s("%d", &n);

	// 수열 입력
	for (i = 0; i < n; i++)
		scanf_s("%d", &a[i]);

	// 연산자 개수
	for (i = 0; i < 4; i++)
		scanf_s("%d", &op[i]);

	DFS(1, a[0]);
	printf("%d\n%d\n", maxi, mini);
}

• L이 n이 될때까지 모든 연산자의 개수가 0이 될때까지 사용하여 그 결과값을 전달하여 정답을 구합니다.