반응형
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
|
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
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int n;
int arr[11];
int op[4];
int op_arr[10];
int max_val = -987654321;
int min_val = 987654321;
stack<int> s;
stack<int> temp;
void insertData() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < 4; i++)
cin >> op[i];
}
void initData() {
for (int i = n - 1; i >= 0; i--)
temp.push(arr[i]);
int idx = 0;
for (int i = 0; i < 4; i++) {
while (op[i] > 0) {
op_arr[idx++] = i;
op[i]--;
}
}
}
void func() {
s = temp;
int op_idx = 0;
while (s.size() > 1) {
int result;
int a = s.top();
s.pop();
int b = s.top();
s.pop();
if (op_arr[op_idx] == 0)
result = a + b;
else if (op_arr[op_idx] == 1)
result = a - b;
else if (op_arr[op_idx] == 2)
result = a * b;
else if (op_arr[op_idx] == 3)
result = a / b;
s.push(result);
op_idx++;
}
int ret = s.top();
s.pop();
min_val = min(min_val, ret);
max_val = max(max_val, ret);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
insertData();
initData();
func();
while (next_permutation(op_arr, op_arr + (n - 1)))
func();
cout << max_val << '\n' << min_val;
}
|
cs |
백트래킹 사용
|
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
|
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int n;
int arr[11];
int op[4];
int max_val = -987654321;
int min_val = 987654321;
// cnt: 연산 횟수
void dfs(int temp_val, int cnt) {
if (cnt == n - 1) {
min_val = min(min_val, temp_val);
max_val = max(max_val, temp_val);
return;
}
// 백트래킹 부분
for (int i = 0;i < 4;i++) {
if (op[i] != 0) {
--op[i]; // 사용한 연산자는 개수 빼야함
if (i == 0)
dfs(temp_val + arr[cnt + 1], cnt+1);
else if(i == 1)
dfs(temp_val - arr[cnt + 1], cnt + 1);
else if (i == 2)
dfs(temp_val * arr[cnt + 1], cnt + 1);
else if (i == 3)
dfs(temp_val / arr[cnt + 1], cnt + 1);
++op[i]; // 다음 탐색을 위해서 연산자 개수 복구
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < 4; i++)
cin >> op[i];
dfs(arr[0], 0);
cout << max_val << '\n' << min_val;
}
|
cs |
반응형