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

연산자 끼워넣기

문제 링크

연산자 끼워넣기

분석

입력으로 첫 번째 줄에 수열의 크기 N이 주어지고, 두 번째 줄에 수와 수 사이에 끼워넣어 연산할 연산자가 N-1개 주어집니다.

수열에 주어지는 연산자를 이용해 만들 수 있는 식의 개수를 반환하는 문제입니다.

숫자의 순서는 바꾸지 못하며, 주어진 연산자 개수만큼 써서 가능한 모든 연산자 배치를 만들어야합니다.
이후 모든 경우의 수 중에서 결과 값의 최댓값과 최솟값을 구해 출력해야합니다.

식 계산에서 연산자의 우선순위는 일반적인 우선순위가 아니라 앞에서부터 순서대로 진행합니다.
즉, 곱셈과 나눗셈이 우선이 아닌 왼쪽부터 오른쪽으로 순서대로 진행하게 됩니다.

예를 들어 $3 + 6 - 7 \times 3$일 경우 $7 \times 3$부터 하는 것이 아닌 $3 + 6$부터 순서대로 진행합니다.

해당 문제는 백트래킹으로 풀이할 수 있습니다.
연산자 4개 중 남아있는 연산자를 하나 골라 모든 경우의 수를 탐색해야 하기 때문입니다.

풀이

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 결과의 최대값/최소값을 전역으로 관리한다.
int maxNum = INT_MIN;
int minNum = INT_MAX;

// 백트래킹 함수
// numList: 숫자 리스트(고정)
// operatorList: 남아 있는 연산자 개수
// curResult: 현재까지 계산된 결과
// numListIndex: 다음에 사용할 숫자의 인덱스
void backtrack(const vector<int>& numList, vector<int>& operatorList, int curResult, int numListIndex)
{
	// 종료 조건: 모든 숫자를 다 사용한 경우
	if (numListIndex >= numList.size())
	{
		// 최댓값 및 최솟값 갱신
		maxNum = (maxNum > curResult) ? maxNum : curResult;
		minNum = (minNum > curResult) ? curResult : minNum;

		return;
	}

	// 4가지 연산자를 순서대로 시도하는 반복문
	for (int operIndex = 0; operIndex < operatorList.size(); ++operIndex)
	{
		// 해당 연산자를 사용할 수 있는 경우
		if (operatorList[operIndex] > 0) --operatorList[operIndex];
		// 사용할 수 없는 경우 스킵
		else continue;
	
		// 현재 결과를 기반으로 다음 결과를 계산한다.
		int nextResult = curResult;
		
		switch (operIndex)
		{
		case 0: // +
			nextResult += numList[numListIndex];
			break;
		case 1: // -
			nextResult -= numList[numListIndex];
			break;
		case 2: // *
			nextResult *= numList[numListIndex];
			break;
		case 3: // /
			// 나눗셈은 정수 몫만 취하며, 음수는 양수로 나눗셈을 하고, 음수로 변경한다.
			if (curResult < 0) nextResult = -(-nextResult / numList[numListIndex]);
			else nextResult /= numList[numListIndex];
			break;
		default:
			break;
		}
		
		// 다음 숫자로 넘어가기 위한 재귀 호출
		backtrack(numList, operatorList, nextResult, numListIndex + 1);
		
		// 사용했던 연산자 복구
		++operatorList[operIndex];
	}
}

int main()
{
	int n;
	std::cin >> n;

	vector<int> numList(n);
	
	// 숫자 입력을 받는 반복문
	for (int i = 0; i < n; ++i)
	{
		int temp;
		std::cin >> temp;
		numList[i] = temp;
	}

	vector<int> operatorList(4);
	
	// 연산자 개수를 입력받는 반복문
	for (int i = 0; i < 4; ++i)
	{
		int temp;
		std::cin >> temp;
		operatorList[i] = temp;
	}

	// 함수 호출
	backtrack(numList, operatorList, numList[0], 1);

	std::cout << maxNum << std::endl;
	std::cout << minNum << std::endl;
}

성능 요약

시간 복잡도는 $O((n - 1) \times 4^{n-1})$입니다.

• 재귀 호출의 경우의 수 $O(4^{n-1})$
  • 반복문으로 4개의 연산자를 확인 $O(4)
  • 함수 깊이 $O(n - 1)$

공간 복잡도는 $O(n)$입니다.

• 함수 스택 공간 $(n)$
• 입력을 저장하는 배열 numList $O(n)$
• 입력을 저장하는 배열 operatorList $O(4) \approx O(1)$
• $O(n) + O(n) + O(1)$

메모리: 2020 KB

시간: 0 ms