[BOJ]14888번: 연산자 끼워넣기 (c++)

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

14888번: 연산자 끼워넣기

 

방법 1: 순열로 연산자 순서를 바꾸면서 결과값 계산

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

// 답안의 범위가 -10억 ~ 10억
int max_num = numeric_limits<int>::min();
int min_num = numeric_limits<int>::max();

// 주어진 연산자 배열로 계산
int calc(vector<int> &nums, vector<int> &strg)
{
	int sum = nums[0];
	for (int i = 0; i < strg.size(); ++i)
	{
		int op = strg[i];
		if (op == 0)
		{
			sum += nums[i + 1];
		}
		else if (op == 1)
		{
			sum -= nums[i + 1];
		}
		else if (op == 2)
		{
			sum *= nums[i + 1];
		}
		else if (op == 3)
		{
			sum /= nums[i + 1];
		}
	}
	return sum;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<int> nums(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> nums[i];
	}

	vector<int> strg(N - 1);
	int idx = 0;
	for (int i = 0; i < 4; ++i)
	{
		int cnt;
		cin >> cnt;
		while (cnt--)
		{
			strg[idx++] = i;
		}
	}

	// 순열로 가능한 모든 결과값을 구해서 최대값/최소값 결정하기
	do {

		int res = calc(nums, strg);

		max_num = max(res, max_num);
		min_num = min(res, min_num);

	} while (next_permutation(strg.begin(), strg.end()));

	// 출력
	cout << max_num << '\n';
	cout << min_num << '\n';

	return 0;
}

 

 

방법 2 : + - x % 중 하나를 연산하면 연산 횟수를 차감하는 방식으로 백트랙킹

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

// 답안의 범위가 -10억 ~ 10억
int max_num = numeric_limits<int>::min();
int min_num = numeric_limits<int>::max();

// 주어진 연산자 인덱스로 계산
int calc(int op, int num1, int num2)
{
	if (op == 0)
	{
		return num1 + num2;
	}
	else if (op == 1)
	{
		return num1 - num2;
	}
	else if (op == 2)
	{
		return num1 * num2;
	}
	else if (op == 3)
	{
		return num1 / num2;
	}
	return 0;
}

void dfs(vector<int> &nums, vector<int> &strg, int res, int depth)
{
	if (depth == nums.size())
	{
		max_num = max(max_num, res);
		min_num = min(min_num, res);
		return;
	}

	for (int j = 0; j < 4; ++j)
	{
		// 연산 가능한 횟수가 남아있으면
		if (strg[j] > 0)
		{
			--strg[j];
			// 이전 결과와 현재숫자를 연산한 값으로 dfs함수 재귀호출
			dfs(nums, strg, calc(j, res, nums[depth]), depth + 1);
			++strg[j];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<int> nums(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> nums[i];
	}

	vector<int> strg(4);
	for (int i = 0; i < 4; ++i)
	{
		cin >> strg[i];
	}

	// 백트랙킹으로 가능한 모든 수를 구해서 최대값/최소값 결정하기
	dfs(nums, strg, nums[0], 1);

	// 출력
	cout << max_num << '\n';
	cout << min_num << '\n';

	return 0;
}

 

 

복병은 범위다

연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

max_num, min_num의 초기값을 어떻게 설정하는지가 중요하다!