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

문제 출처: www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

1. 코드

#include <iostream>
#include <vector>

using namespace std;

vector <int> operand;	//피연산자 저장
vector <int> op;	//연산자 저장
vector <bool> flag;	//연산자 사용여부
int low = 100000000;	//최솟값
int hight = -100000000;	//최댓값
int AC = 0;		//계산 결과

void solution(int a)
{
	if (a == op.size())
	{
		if (hight < AC) hight = AC;	//계산 결과가 크다면
		if (low > AC) low = AC;		//계산 결과가 작다면
		return;
	}
	if (a == 0) AC = operand[0];		//첫 계산일 경우 첫 번째 피연산자로 초기화
	for (int i = 0; i < op.size(); i++)	
	{
		if (flag[i]) continue;		//해당 연산자를 사용하였는가?
		int buffer = AC;		//재귀 함수 종료에 따른 AC 백업

		switch (op[i])			//연산자에 맞춰서 계산
		{
		case 0:
			AC += operand[a + 1];
			break;
		case 1:
			AC -= operand[a + 1];
			break;
		case 2:
			AC *= operand[a + 1];
			break;
		case 3:
			AC /= operand[a + 1];
		default:
			break;
		}

		flag[i] = true;		//연산자 사용 처리
		solution(a + 1);

		AC = buffer;		//계산 결과 백업
		flag[i] = false;	//연산자 미사용 처리
	}
}

int main(void)
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		operand.push_back(num);		//피연산자 저장
	}

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

		if (operation)
		{
			for(int j = 0; j < operation; j++)
			{
				flag.push_back(false);	//연산자 사용여부 저장
				switch (i)
				{
				case 0:		// +
					op.push_back(0);
					break;
				case 1:		// -
					op.push_back(1);
					break;
				case 2:		// ×
					op.push_back(2);
					break;
				case 3:		// ÷
					op.push_back(3);
					break;
				default:
					break;
				}
			}
		}
	}
	solution(0);

	cout << hight << endl << low;
	return 0;
}

(실행)

2. 풀이

백트래킹과 switch문 그리고 vector를 이용하여 문제를 해결하였다.

vector <int> operand;	//피연산자 저장
vector <int> op;	//연산자 저장
vector <bool> flag;	//연산자 사용여부
int low = 100000000;	//최솟값
int hight = -100000000;	//최댓값
int AC = 0;		//계산 결과

먼저 문제 해결에 필요한 것들을 전역변수로 정의한다.

int n;
cin >> n;

for (int i = 0; i < n; i++)
{
	int num;
	cin >> num;
	operand.push_back(num);		//피연산자 저장
}

그리고 수의 갯수(n)를 입력받고 입력된 수 만큼 식에 사용될 수를 입력하고 그 값을 operand에 push해준다.

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

	if (operation)
	{
		for(int j = 0; j < operation; j++)
		{
			flag.push_back(false);	//연산자 사용여부 저장
			switch (i)
			{
			case 0:		// +
				op.push_back(0);
				break;
			case 1:		// -
				op.push_back(1);
				break;
			case 2:		// ×
				op.push_back(2);
				break;
			case 3:		// ÷
				op.push_back(3);
				break;
			default:
				break;
			}
		}
	}
}
solution(0);

cout << hight << endl << low;
return 0;

연산자의 횟수를 입력하는데 만약 0이 아니라면 입력한 횟수만큼 반복문으로 해당하는 연산자를 op에 push해주고, flag에도 false를 push해준다. 연산자의 구분은 +(0), -(1), ×(2), ÷(3)으로 구분한다. 그리고 solution을 실행하는데

void solution(int a)
{
	if (a == op.size())
	{
		if (hight < AC) hight = AC;	//계산 결과가 크다면
		if (low > AC) low = AC;		//계산 결과가 작다면
		return;
	}
    
	if (a == 0) AC = operand[0];		//첫 계산일 경우 첫 번째 피연산자로 초기화
	
	for (int i = 0; i < op.size(); i++)	
	{
		if (flag[i]) continue;		//해당 연산자를 사용하였는가?
		int buffer = AC;		//재귀 함수 종료에 따른 AC 백업

		switch (op[i])			//연산자에 맞춰서 계산
		{
		case 0:
			AC += operand[a + 1];
			break;
		case 1:
			AC -= operand[a + 1];
			break;
		case 2:
			AC *= operand[a + 1];
			break;
		case 3:
			AC /= operand[a + 1];
		default:
			break;
		}

		flag[i] = true;		//연산자 사용 처리
		solution(a + 1);

		AC = buffer;		//계산 결과 백업
		flag[i] = false;	//연산자 미사용 처리
	}
}

최종적인 결과가 나올 때 hight보다 연산 결과인 AC가 더 크면 hight 변수를 AC로 초기화하고 low도 마찬가지로 AC보다 작다면 AC로 초기화 시켜준다.

결과가 나오지않고, 첫 번째 연산일 경우 AC에 operand의 첫 번째 요소를 저장한 뒤 사용하지않은 연산자를 사용하여 연산시키고 AC에 적재한다. 그리고 해당 연산자는 flag를 이용하여 사용했다는 것을 표시해준다. 그리고 재귀 함수를 호출하는데 재귀 함수가 종료된다면 해당하는 AC의 값을 이전의 상태로 돌려야하기 때문에 buffer라는 변수를 이용하여 AC를 이전의 값으로 되돌린다. 그리고 해당하는 연산자를 다시 사용할 수 있게 flag의 값을 true로 전환한다.

이 과정들을 통해 제일 작은 값과 큰 값이 구해지고 그것을 출력하면 된다.