[C++] 14888. 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

풀이

 

유의한 점

1. long long 형 사용

  - 계산된 결과가 -10억 ~ 10억 사이의 값이라고 하여 long long형을 활용함. 

2. 재귀 함수 활용

  - 자기 자신 호출(루프)

  - 탈출문

3. 전역변수 활용

  - 일반적으론 매개변수로 넘기는 것이 맞지만, 코테에서만큼은 전역변수를 활용하는 것이 좋다는 이야기를 들어 전역변수를 활용함.

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

using namespace std;

long long int max_num, min_num;
int num_cnt;
vector<int> num_list;
vector<int> opr_list;

void initiator()
{

	int temp = 0;
	max_num = LONG_MIN;
	min_num = LONG_MAX;

	cin >> num_cnt;
	for (int i = 0; i < num_cnt; i++)
	{
		cin >> temp;
		num_list.push_back(temp);
	}
	for (int i = 0; i < 4; i++)
	{
		cin >> temp;
		opr_list.push_back(temp);
	}
}

int opr_func(long long int num1, long long int num2, int op_num)
{
	if (op_num == 0)
		num1 += num2;
	else if (op_num == 1)
		num1 -= num2;
	else if (op_num == 2)
		num1 *= num2;
	else if (op_num == 3)
		num1 /= num2;
	return num1;
}

void solution(long long int n, long long int sum)
{
	if (n == num_cnt)
	{
		max_num = max(sum, max_num);
		min_num = min(sum, min_num);
		return;
	}
	for (int j = 0; j < 4; j++)
	{
		if (opr_list[j] == 0)
			continue;
		opr_list[j]--;
		solution(n + 1, opr_func(sum, num_list[n], j));
		opr_list[j]++;
	}

}

int main(void)
{
	initiator();
	solution(1, num_list[0]);
	cout << max_num << "\n" << min_num;
}

---

처음 생각했던 알고리즘 및 문제점

1. sum의 값을 복구 안함.

재귀로 호출할 때는 복구 코드를 추가해야하는데, 이를 추가하면 복잡해짐.

자기 자신을 호출하는 코드에 연산 코드를 넣음으로써 복구 코드를 추가 하지 않도록 개선함.

 

2. max, min 사용시 초기값

일반적으로 초기값 사용시 min, max에 0을 넣어서 사용해왔음.

이런 경우 에러가 날 수 있기 때문에 climits 라이브러리를 include 활용하였음.

#include <iostream>
#include <vector>

using namespace std;

long long max_num;
long long min_num;

void initiator(vector<int> num_list, vector<int> opr_list, int *num_cnt)
{
	
	int temp = 0;
	max_num = 0; // 초기화를 0으로 함으로써 에러 발생 가능성 존재.
	min_num = 0;


	cin >> *num_cnt;
	for (int i = 0; i < *num_cnt; i++)
	{
		cin >> temp;
		num_list.push_back(temp);
	}
	for (int i = 0; i < 4; i++)
	{
		cin >> temp;
		opr_list.push_back(temp);
	}
}


void solution(vector<int> num_list, vector<int> opr_list, int init_num, int num_cnt, int sum)
{
	if (num_cnt == 1)
	{
		if (sum >= max_num)
			max_num = sum;
		else if (sum <= min_num)
			min_num = sum;

		if (max_num == 0)
			max_num = min_num;
		else if (min_num == 0)
			min_num = max_num;
	}
	for (int i = init_num; i <= num_cnt; i++)
	{

		for (int j = 0; j < 4; j++)
		{
			if (opr_list[j] == 0)
				continue;
			if (j == 0)
				sum += num_list[i];
			else if (j == 1)
				sum -= num_list[i];
			else if (j == 2)
				sum *= num_list[i];
			else if (j == 3)
				sum /= num_list[i];
			opr_list[j]--;
			solution(num_list, opr_list, init_num + 1, num_cnt - 1, sum); // 값을 복구를 안해줌.
		}
	}
}

int main(void)
{
	int num_cnt = 0;
	vector<int> num_list;
	vector<int> opr_list;
	//initiator(num_list, opr_list, &num_cnt);
	int temp = 0;
	max_num = 0;
	min_num = 0;


	cin >> num_cnt;
	for (int i = 0; i < num_cnt; i++)
	{
		cin >> temp;
		num_list.push_back(temp);
	}
	for (int i = 0; i < 4; i++)
	{
		cin >> temp;
		opr_list.push_back(temp);
	}
	solution(num_list, opr_list, 1, num_cnt, num_list[0]);
	cout << max_num << "\n" << min_num;
}