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

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

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

연산자는 +, -, *, /

총 4개가 가능하고 그 개수는 입력으로 주어진다. 수의 개수의 최대 크기가 11로 작고

특별한 조건으로 값을 구하는 게 아니므로 완전탐색을 이용해서 문제를 해결할 수 있다.

 

나는 순열을 이용해서 N-1개의 기호를 뽑아 값을 계산한 후 최대값과 최소값을 갱신하는 방법으로 문제를 해결하였다.

처음에는 조합처럼 해결하려했으나 그렇게 하면 연산자의 위치를 정하는게 오류가 생겨 순열로 하였고, 순열로 하는 방법이 정답인 것 같다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>
#define ll long long
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MAX 100000 + 1
#define endl '\n'

using namespace std;

int N;
int maxV = -INF, minV = INF;
int od[12];
int op[4];
int Sop[12];

void func(int depth, int start) {
	if (depth == N - 1) {
		int total = 0, Temp;
		stack<pair<int,int>> stk;
		stk.push({ od[0], 0 });
		for (int i = 0; i < N-1; i++) {
			int x = stk.top().first;
			int idx = stk.top().second;
			stk.pop();

			if (Sop[i] == 0) {
				Temp = x + od[idx + 1];
			}
			else if (Sop[i] == 1) {
				Temp = x - od[idx + 1];
			}
			else if (Sop[i] == 2) {
				Temp = x * od[idx + 1];
			}
			else {
				Temp = x / od[idx + 1];
			}
			stk.push({ Temp, idx + 1 });
		}
		int data = stk.top().first;
		maxV = max(maxV, data);
		minV = min(minV, data);
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (op[i]) {
			Sop[depth] = i;
			op[i]--;

			func(depth + 1, i);

			op[i]++;
		}
	}
}

int main() {
	CUNLINK;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> od[i];
	for (int i = 0; i < 4; i++) cin >> op[i];
	func(0, 0);
	cout << maxV << endl << minV;
	
	return 0;
}