연산자 끼워넣기 (2) - 15658

문제 : https://www.acmicpc.net/problem/15658

15658번: 연산자 끼워넣기 (2)

 

코드 :

#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int num[11];
int mon[4];
bool check[44] = { false };
int m = 0;
int n = 0;
int numMax = INT32_MIN;
int numMin = INT32_MAX;

int calculation(int v1, int v2, int mIndex)
{
	int f = 0;
	int i;
	for (i = 0; i < 4; i++)
	{
		f += mon[i];
		if (mIndex < f)
		{
			break;
		}
	}
	int result = 0;
	if (i == 0)
	{
		result = v1 + v2;
	}
	else if (i == 1)
	{
		result = v1 - v2;
	}
	else if (i == 2)
	{
		result = v1 * v2;
	}
	else if (i == 3)
	{
		result = v1 / v2;
	}
	return result;
}

void solution(int mIndex, int nIndex, int calc)
{
	//탈출조건
	if (mIndex > m)
	{
		return;
	}
	//성공조건
	if (nIndex == n)
	{
		if (numMax < calc)
		{
			numMax = calc;
		}
		if (numMin > calc)
		{
			numMin = calc;
		}
		return;
	}
	for (int i = 0; i < m; i++)
	{
		if (check[i]) continue;
		int v = calculation(calc, num[nIndex], i);
		check[i] = true;
		solution(i + 1, nIndex + 1, v);
		check[i] = false;
	}
}

int main()
{
	cin >> n;
	//숫자입력
	for (int i = 0; i < n; i++)
	{
		cin >> num[i];
	}
	//연사자 갯수 입력
	for (int i = 0; i < 4; i++)
	{
		cin >> mon[i];
		m += mon[i];
	}
	solution(0, 1, num[0]);
	cout << numMax << "\n" << numMin << "\n";
	return 0;
}

해당 인덱스의 산술연산 기호를 사용했는지 확인하는 check배열을 만들어서 재귀함수를 사용하였다.

불필요한 for문을 몇 번 반복하지만 continue를 통해 큰 문제없을 것으로 판단되었는데.. 시간초과가...

함수호출이 생각보다 많이 속도를 먹는건지..

해서 일단 불필요한 반복을 하지않도록 코드를 수정하였다.

코드(RE) :

#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int num[11];
int mon[4];
int n = 0;
int numMax = INT32_MIN;
int numMin = INT32_MAX;

void solution(int nCount, int plus, int minus, int mul, int div, int value)
{
	if (nCount == n)
	{
		if (numMax < value)
			numMax = value;
		if (numMin > value)
			numMin = value;
		return;
	}

	if (plus > 0)
	{
		solution(nCount + 1, plus - 1, minus, mul, div, value + num[nCount]);
	}
	if (minus > 0)
	{
		solution(nCount + 1, plus, minus - 1, mul, div, value - num[nCount]);
	}
	if (mul > 0)
	{
		solution(nCount + 1, plus, minus, mul - 1, div, value * num[nCount]);
	}
	if (div > 0)
	{
		solution(nCount + 1, plus, minus, mul, div - 1, value / num[nCount]);
	}
}
int main()
{
	cin >> n;
	//숫자입력
	for (int i = 0; i < n; i++)
	{
		cin >> num[i];
	}
	//연사자 갯수 입력
	for (int i = 0; i < 4; i++)
	{
		cin >> mon[i];
	}
	solution(1, mon[0], mon[1], mon[2], mon[3], num[0]);
	cout << numMax << "\n" << numMin << "\n";
	return 0;
}