(c++)백준 14888번: 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

[풀이]

주어진 연산자를 나열하는 모든 경우에 대해 계산을 하고, 최소값과 최대값을 저장한다.

 

#include <iostream>
#include <vector>
#include <algorithm>//min,max
using namespace std;

int N;
vector<int>A(11);//N개의 수
int op[4];//각 연산자의 개수 (0:+, 1:-, 2:*, 3:/)
vector<int>v;//식에 쓸 연산자 순서대로 넣기
int Min = 10e10;
int Max = -10e10;

int Calc() {
	int res = A[0];
	for (int i = 0; i < N - 1; i++) {
		//덧셈일 경우
		if (v[i] == 0) {
			res += A[i + 1];
		}
		//뺄셈일 경우
		else if (v[i] == 1) {
			res -= A[i + 1];
		}
		//곱셈일 경우
		else if (v[i] == 2) {
			res *= A[i + 1];
		}
		//나눗셈일 경우
		else if (v[i] == 3) {
			res /= A[i + 1];
		}
	}
	return res;
}

//연산자 나열하는 모든 경우 구하기
void getSet(int cnt) {
	if (cnt == N - 1) {
		int res = Calc();
		Min = min(Min, res);
		Max = max(Max, res);
		return;
	}

	if (op[0] > 0) {
		op[0]--;
		v.push_back(0);
		getSet(cnt + 1);
		v.pop_back();
		op[0]++;
	}

	if (op[1] > 0) {
		op[1]--;
		v.push_back(1);
		getSet(cnt + 1);
		v.pop_back();
		op[1]++;
	}

	if (op[2] > 0) {
		op[2]--;
		v.push_back(2);
		getSet(cnt + 1);
		v.pop_back();
		op[2]++;
	}

	if (op[3] > 0) {
		op[3]--;
		v.push_back(3);
		getSet(cnt + 1);
		v.pop_back();
		op[3]++;
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < 4; i++) {
		cin >> op[i];
	}
	getSet(0);
	cout << Max << '\n';
	cout << Min << '\n';
}

int main() {
	solution();
	return 0;
}