Problem
Problem URL : 연산자 끼워넣기
[1] Answer Code (18. 10. 05)
#include<iostream>
#include<algorithm>
using namespace std;
int maxN = -100000000, minN = 1000000000;
int n, a[12], p, s, m, d;
void go(int index, int plus, int sub, int multi, int divi, int total) {
if (index == n) {
maxN = max(maxN, total);
minN = min(minN, total);
return;
}
if (plus < p)
go(index + 1, plus + 1, sub, multi, divi, total + a[index]);
if (sub < s)
go(index + 1, plus, sub + 1, multi, divi, total - a[index]);
if (multi < m)
go(index + 1, plus, sub, multi + 1, divi, total * a[index]);
if (divi < d)
go(index + 1, plus, sub, multi, divi + 1, total / a[index]);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
cin >> p >> s >> m >> d;
go(1, 0, 0, 0, 0, a[0]);
cout << maxN << endl << minN << endl;
return 0;
}
Review
- DFS
[2] Answer Code (18. 10. 16)
#include<iostream>
#include<vector>
using namespace std;
int oper[4];
int n;
int ans_min;
int ans_max;
vector<int> v;
void dfs(int idx, int sum){
if( idx == (int) v.size() ){
ans_min = ans_min < sum ? ans_min : sum;
ans_max = ans_max < sum ? sum : ans_max;
return ;
}
if( oper[0] > 0 ){
oper[0] --;
dfs(idx+1,sum + v[idx]);
oper[0] ++;
}
if( oper[1] > 0 ){
oper[1] --;
dfs(idx+1,sum - v[idx]);
oper[1] ++;
}
if( oper[2] > 0 ){
oper[2] --;
dfs(idx+1,sum * v[idx]);
oper[2] ++;
}
if( oper[3] > 0 ){
oper[3] --;
dfs(idx+1,sum / v[idx]);
oper[3] ++;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ans_min = 2e9;
ans_max = -2e9;
cin >> n;
for(int i=0; i<n; i++){
int tmp;
cin >> tmp;
v.push_back(tmp);
}
for(int i=0; i<4; i++){
cin >> oper[i];
}
dfs(1,v[0]);
cout << ans_max << endl;
cout << ans_min << endl;
return 0;
}
Review
-
기초적인 DFS 문제
-
처음에 ans_max 값을 -1로 초기화하는 실수를 했다.