[백준/BOJ] 15658번 연산자 끼워넣기 (2) (C++)

www.acmicpc.net/problem/15658

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

14888번과 동일한 문제인데, 연산자의 개수가 n-1개가 아닌 최대 4n개까지 입력받을 수 있는 것이 달랐습니다. 처음에 next_permutation을 이용하여 접근했는데, 시간복잡도가 44C11 * 11 이라 시간초과가 발생하였습니다. 그래서 14888번의 동일한 풀이에 연산을 할 때 마다 연산자를 기록할 수 있게 벡터를 하나 생성하여 해결했습니다.

 

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

int n, maxx = -2147000000, minn = 2147000000;
int a[12], op[4];
vector<int> v;

void DFS(int idx) {
	if(idx == n - 1) {
		int sum = a[0];
		for(int i = 0; i < v.size(); i++) {
			if(v[i] == 0) sum += a[i + 1];
			else if(v[i] == 1) sum -= a[i + 1];
			else if(v[i] == 2) sum *= a[i + 1];
			else sum /= a[i + 1]; 
		}
        
		maxx = max(maxx, sum);
		minn = min(minn, sum);
		return;
	} else {
		if(op[0] > 0) {
			op[0]--;
			v.push_back(0);
			DFS(idx + 1);
			v.pop_back();
			op[0]++;
		}
        
		if(op[1] > 0) {
			op[1]--;
			v.push_back(1);
			DFS(idx + 1);
			v.pop_back();
			op[1]++;
		}
        
		if(op[2] > 0) {
			op[2]--;
			v.push_back(2);
			DFS(idx + 1);
			v.pop_back();
			op[2]++;
		}
        
		if(op[3] > 0) {
			op[3]--;
			v.push_back(3);
			DFS(idx + 1);
			v.pop_back();
			op[3]++;
		}
	}
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
    	cin >> a[i];
	}
	for(int i = 0; i < 4; i++) {
		cin >> op[i];
	}
	
	DFS(0);
	cout << maxx << "\n" << minn;
}