[Baekjoon] 14888번: 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

---

 

문제 해결 과정

착안

연산자 우선순위가 아닌, 연산이 주어지는 순서대로 순차적으로 계산하는 문제이고 주어지는 연산자의 종류나 수를 알 수 없기 때문에 최댓값, 최솟값을 구하기 위해서는 모든 경우에 대해 계산을 해야한다고 판단하여 백트래킹(퇴각검색) 알고리즘으로 구현하고자 하였다.

 

구현

각각의 사칙연산에 대한 연산을 수행하는 함수를 만들어 문제를 해결하고자 하였다. 연산 함수(int Operation())에서는 주어진 연산의 남아있는 연산자의 수가 0보다 클 때, 연산자의 수를 감소시킨 다음 연산을 수행한 다음 네 종류의 연산을 재귀적으로 수행하도록 함수를 구현하였다. 백트래킹을 위해서 네 종류의 연산을 모두 수행하고 난 뒤에는 현재 함수에서 사용한 연산자의 수를 다시 증가한 다음 연산 전의 결과를 반환하도록 하였다. 모든 연산자가 사용되었을 때 식이 완성되므로, 이때 연산 최종 결과를 가지고 최대 / 최소값을 갱신하도록 구현하였다.

 

코딩 편의상 enum class를 선언하여 연산 종류를 구분하였으며, switch-case 구문을 사용하여 연산 함수 내에서 주어진 연산을 구분하여 수행하도록 구현하였다. 전역 변수를 사용하는 걸 별로 좋아하지 않아서 지역 변수만을 사용하도록 함수를 짰더니 매개변수 전달 코드가 길어지고, 가독성이 조금 좋지는 않은 것 같다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

enum class OPERATION
{
	Add,
	Subtract,
	Multiplication,
	Division
};

void Operation(const vector<int>& numbers, int operators[4], OPERATION operation, int numOp, int result, int& Min, int& Max)
{
	if (operators[(int)operation] <= 0)
		return;

	int temp = result;
	operators[(int)operation]--;

	switch (operation)
	{
		case OPERATION::Add:
			result += numbers[numOp];
			break;
		case OPERATION::Subtract:
			result -= numbers[numOp];
			break;
		case OPERATION::Multiplication:
			result *= numbers[numOp];
			break;
		case OPERATION::Division:
			result /= numbers[numOp];
			break;
	}

	if (numOp == (int)numbers.size() - 1)
	{
		Max = result > Max ? result : Max;
		Min = result < Min ? result : Min;
	}
	else
	{
		Operation(numbers, operators, OPERATION::Add, numOp + 1, result, Min, Max);
		Operation(numbers, operators, OPERATION::Subtract, numOp + 1, result, Min, Max);
		Operation(numbers, operators, OPERATION::Multiplication, numOp + 1, result, Min, Max);
		Operation(numbers, operators, OPERATION::Division, numOp + 1, result, Min, Max);
	}

	operators[(int)operation]++;
	return;
}

void FindMinMax(const vector<int>& numbers, int operators[4], int& Min, int& Max)
{	
	Operation(numbers, operators, OPERATION::Add, 1, numbers[0], Min, Max);
	Operation(numbers, operators, OPERATION::Subtract, 1, numbers[0], Min, Max);
	Operation(numbers, operators, OPERATION::Multiplication, 1, numbers[0], Min, Max);
	Operation(numbers, operators, OPERATION::Division, 1, numbers[0], Min, Max);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int N;
	cin >> N;

	vector<int> Numbers(N);
	int Operators[4] = { 0, };
	for (int i = 0; i < N; i++)
		cin >> Numbers[i];

	for (int i = 0; i < 4; i++)
		cin >> Operators[i];

	int Max = -1000000000;
	int Min = 1000000000;
	FindMinMax(Numbers, Operators, Min, Max);
	cout << Max << "\n" << Min << "\n";

	return 0;
}

 

실행 결과

전역 변수를 사용하지 않고 짠 결과, 함수의 매개변수로 계속 전달해야하는 값이 많아서 코드가 길어짐.

전역 변수를 사용하면 코드 자체는 더 깔끔해져 확실히 가독성이 좋아지기는 한다.