문제
https://www.acmicpc.net/problem/15658
문제해설
숫자가 n개 주어지고
+, -, x, / 연산자의 개수가 주어진다.
이때 숫자와 연산자들을 조합하여 최대값과 최소값을 구하면 된다.
연잔자를 다 쓸 필요는 없다.
문제풀이
재귀를 이용해 완전탐색을 해주면 된다.
재귀는 현재 숫자의 인덱스, 연산의 합, 연산자들의 개수를 넘겨주었다.
연산자들의 개수는 벡터로 만들어 벡터 통째로 인자로 넘겼다.
연산자들 4개를 재귀형태로 만들어서 탐색하면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<algorithm>
#include<vector>
#include<limits.h>
using namespace std;
vector<int>arr;
int n, maxx = INT_MIN, minn = INT_MAX;
void calculate(int now, int sum, vector<int>& oper) {
if (now == n - 1) {
maxx = max(maxx, sum);
minn = min(minn, sum);
return;
}
if (now == 0)
sum = arr[0];
int num = arr[now + 1];
if (oper[0] > 0) {
oper[0]--;
calculate(now += 1, sum + num, oper);
oper[0]++;
now--;
}
if (oper[1] > 0) {
oper[1]--;
calculate(now += 1, sum - num, oper);
oper[1]++;
now--;
}
if (oper[2] > 0) {
oper[2]--;
calculate(now += 1, sum * num, oper);
oper[2]++;
now--;
}
if (oper[3] > 0) {
oper[3]--;
calculate(now += 1, sum / num, oper);
oper[3]++;
now--;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
arr.resize(n);
vector<int>oper(4);
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < 4; i++)
cin >> oper[i];
calculate(0, 0, oper);
cout << maxx << "\n" << minn;
return 0;
}