문제
https://www.acmicpc.net/problem/16637
문제해설
수식이 주어지고 그 수식에서 괄호를 만들어 연산했을 때 최대값을 구하는 것이다.
괄호에는 연산자가 하나만 들어갈 수 있다. 숫자 2개만 묶을 수 있다는 소리이다.
그리고 괄호를 제외한 연산에는 우선순위가 없다.
곱하기 연산이 더하기나 빼기보다 우선되지 않고 앞에서부터 차례로 연산한다.
문제풀이
어떻게 접근해야하는지 막막했던 문제였다.
괄호를 하나하나 만들어보았다.
예를들어 연산자 5개가 있다면 연산자 기준으로
괄호가 한개라면 1 2 3 4 5
두개라면 13 14 15 24 25 35
세개라면 135
이런식으로 묶을 수 있다.
무슨소린지 잘 모르겠다면 직접 해보면 알 수 있다.
나온 결과를 보니 이웃하는 숫자가 없는 조합이다.
그래서 bfs를 이용해 조합을 다 만들어주고
chk함수를 통해 이웃하는 수가 있는 조합은 다 버렸다.
그 후에 order함수가 괄호가 있는 수들을 계산해서 괄호가 없는 식으로 다시 바꿔주었다.
마지막으로 calculate함수가 식을 계산해주고 최대값을 갱신한다.
뭔가 좀 비효율적으로 짠 느낌이 있는 코드이다.
실력이 더 늘면 그때는 좀더 깔끔하고 간결하게 짤 수 있지 않을까
전체코드
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<limits.h>
using namespace std;
bool visited[20];
vector<int>num;
vector<char>oper(1);
vector<string>cal;
int res = INT_MIN;
void calculate() {
int sum = stoi(cal[0]);
for (int i = 1; i < cal.size(); i++) {
if (cal[i] == "+")
sum += stoi(cal[i + 1]);
else if (cal[i] == "-")
sum -= stoi(cal[i + 1]);
else if (cal[i] == "*")
sum *= stoi(cal[i + 1]);
i++;
}
res = max(res, sum);
cal.clear();
}
void order() {
for (int i = 1; i <= num.size(); i++) {
if (visited[i]) {
int n1, n2;
n1 = num[i - 1];
n2 = num[i];
int tmp;
if (oper[i] == '+')
tmp = n1 + n2;
else if (oper[i] == '-')
tmp = n1 - n2;
else
tmp = n1 * n2;
cal.push_back(to_string(tmp));
if (i == num.size() - 1) continue;
string t = "";
t += oper[i + 1];
cal.push_back(t);
i++;
}
else {
cal.push_back(to_string(num[i - 1]));
if (i == num.size()) continue;
string t = "";
t += oper[i];
cal.push_back(t);
}
}
calculate();
}
void chk() {
for (int i = 2; i < num.size(); i++) {
if (visited[i] && visited[i - 1])
return;
}
order();
}
void dfs(int idx, int cnt, int max) {
if (cnt == max) {
chk();
return;
}
for (int i = idx; i < oper.size(); i++) {
if (visited[i]) continue;
visited[i] = true;
dfs(i, cnt + 1, max);
visited[i] = false;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
for (int i = 0; i < n; i++) {
char x; cin >> x;
if (n == 1) {
cout << x;
return 0;
}
if (i % 2 == 1)
oper.push_back(x);
else
num.push_back(x - '0');
}
int max;
if (num.size() % 2 == 0)
max = num.size() / 2;
else
max = num.size() / 2 + 1;
for (int i = 1; i <= max; i++)
dfs(1, 0, i);
cout << res;
return 0;
}