15658 연산자 끼워넣기(2)

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

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

next_permutation으로 간단하게 해결될 문제인 줄 알았지만, 시간초과가 났다...

next_permutation은 순열을 만드는 함수이기 때문에 O(n!)으로 동작하고, 시간복잡도를 계산해보니 최대 44!로 초과가 날만한 수치였다.

그래서 다른 블로그를 참고하여 재귀방식으로 해결하였다.

핵심은 i번째 인덱스의 연산자 개수가 0보다 크다면, 해당 연산자로 연산한 결과로 재귀 함수를 호출하는 것이다.

이렇게 하면 N - 1개의 숫자 (첫 번째 숫자는 연산할 필요가 없기 때문)에서 4개의 연산자를 선택하는 문제이기 때문에 4^(N - 1)의 시간복잡도를 갖게 된다.

정답코드

//next_permutation : O(n!)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> number;
vector<int> op;
int MinValue = 1e9 + 1, MaxValue = -1e9 - 1;
void dfs(int idx, int plus, int minus, int mul, int div, int sum)
{
	if (idx == N) {
		MinValue = min(sum, MinValue);
		MaxValue = max(sum, MaxValue);
		return;
	}
	if(plus != 0)
		dfs(idx + 1, plus - 1, minus, mul, div, sum + number[idx]);
	if(minus != 0)
		dfs(idx + 1, plus, minus - 1, mul, div, sum - number[idx]);
	if(mul != 0)
		dfs(idx + 1, plus, minus, mul - 1, div, sum * number[idx]);
	if(div != 0)
		dfs(idx + 1, plus, minus, mul, div - 1, sum / number[idx]);
}
int main()
{
	int temp;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		number.push_back(temp);
	}
	for (int i = 0; i < 4; i++) {
		cin >> temp;
		op.push_back(temp);
	}
	dfs(1, op[0], op[1], op[2], op[3], number[0]);
	printf("%d\n%d\n", MaxValue, MinValue);
	return 0;
}