https://www.acmicpc.net/problem/16637
16637번: 괄호 추가하기
첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가
www.acmicpc.net
괄호를 추가하는 게 아니라
브루트포스로 새로운 식을 만들자
치킨 배달 문제를 기억하자
https://larc-en-ciel.tistory.com/129
치킨 배달 - 구현 + 조합(재귀)
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태
larc-en-ciel.tistory.com
|
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
#include <iostream>
#include <vector>
#include <climits>
#include <string>
using namespace std;
int num[15];
char ope[15];
int length;
long ans = 0;
int num_cnt = 0;
int ope_cnt = 1;
vector<int> selected;
void calculate()
{
vector<bool> check(ope_cnt);
for (int idx : selected)
{
check[idx] = true;
}
vector<int> new_num;
vector<char> new_ope;
int check_for_num = 0;
for (int i = 1; i < ope_cnt; i++)
{
if (check[i] == true)
{
if (ope[i] == '+')
{
new_num.push_back(num[i - 1] + num[i]);
check_for_num += 2;
}
else if (ope[i] == '-')
{
new_num.push_back(num[i - 1] - num[i]);
check_for_num += 2;
}
else if (ope[i] == '*')
{
new_num.push_back(num[i - 1] * num[i]);
check_for_num += 2;
}
}
else if(check[i] == false && check[i-1] == true)
{
new_ope.push_back(ope[i]);
}
else
{
new_num.push_back(num[i - 1]);
new_ope.push_back(ope[i]);
check_for_num++;
}
}
if (check_for_num < num_cnt)
{
new_num.push_back(num[num_cnt - 1]);
}
int prob = new_num[0];
for (int i = 0; i < new_ope.size(); i++)
{
if (new_ope[i] == '+')
{
prob += new_num[i + 1];
}
else if (new_ope[i] == '-')
{
prob -= new_num[i + 1];
}
else if (new_ope[i] == '*')
{
prob *= new_num[i + 1];
}
}
if (prob > ans)
{
ans = prob;
}
return;
}
void go(int o_idx)
{
if (o_idx >= ope_cnt)
{
calculate();
return;
}
selected.push_back(o_idx);
go(o_idx + 2);
selected.pop_back();
go(o_idx + 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> length;
string sik;
cin >> sik;
for (int i = 0; i < length; i++)
{
if (isdigit(sik[i]))
{
num[num_cnt] = sik[i] - '0';
num_cnt++;
}
else
{
ope[ope_cnt] = sik[i];
ope_cnt++;
}
}
ans = INT_MIN;
go(1);
cout << ans << '\n';
return 0;
}
|
cs |