Boj15658_연산자 끼어넣기2

Published: December 04, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

boj15658_연산자 끼어넣기2

• 최대값이 무조건 0 이하일거라는 생각을 못해서 많이 틀렸다.

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

int n, arr[11], cntOperator[4];

long long max_num = -1e18, min_num = 1e18;

void go(int idx, long long sum) {
	if (idx >= n) {
		max_num = max(max_num, sum);
		min_num = min(min_num, sum);
	}
	else {

		for (int i = 0; i < 4; i++) {
			if (cntOperator[i]) {
				cntOperator[i]--;
				if (i == 0) go(idx + 1, sum + (long long)arr[idx]);
				if (i == 1) go(idx + 1, sum - (long long)arr[idx]);
				if (i == 2)  go(idx + 1, sum*(long long)arr[idx]);
				if (i == 3)  go(idx + 1, sum / (long long)arr[idx]);
				cntOperator[i]++;
			}
		}
	}
}


int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < 4; i++) {
		scanf("%d", &cntOperator[i]);
	}
	go(1, (long long)arr[0]);
	cout << max_num << endl << min_num;
	return 0;
}