Gidhub BE Developer

# [SW Expert Academy] - 숫자 만들기

2018-04-08
goodGid

## Problem

Problem URL : 숫자 만들기

## [1] Answer Code (18. 08. 28)

``````#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int n;
int card[13];
int max_ans, min_ans;

void dfs(int sum, int idx, int p, int m, int g, int d){
if(idx == n){
if(sum > max_ans)
max_ans = sum;
if(sum < min_ans)
min_ans = sum;
return ;
}
if(p) dfs(sum+card[idx],idx+1,p-1,m,g,d);
if(m) dfs(sum-card[idx],idx+1,p,m-1,g,d);
if(g) dfs(sum*card[idx],idx+1,p,m,g-1,d);
if(d) dfs(sum/card[idx],idx+1,p,m,g,d-1);
}

int main(){
int TC;
cin >> TC;
for (int tc=1; tc<=TC; tc++) {
cin >> n;
max_ans = -2e9;
min_ans = 2e9;

int p,m,g,d;
cin >> p >> m >> g >> d;
for(int i=0; i<n; i++){
scanf("%d",card+i);
}
dfs(card[0],1,p,m,g,d);

printf("#%d %d\n",tc, abs(max_ans - min_ans));
} // end of for tc

return 0;
}
``````

• 20분 컷

## [2] Answer Code (18. 05. 12)

``````#include<iostream>
#include<cstring>
#define ll long long
using namespace std;

int n;
int cal[4];
int arr[12];
ll ans_max,ans_min;

ll func_cal(int idx, int cal_idx, ll sum){
if(cal_idx == 0)
return sum + arr[idx];
else if(cal_idx == 1)
return sum - arr[idx];
else if(cal_idx == 2)
return sum * arr[idx];
else
return sum / arr[idx];
}

void dfs(int idx, ll sum){
if( idx == n-1){
ans_max = ans_max > sum ? ans_max : sum;
ans_min = ans_min > sum ? sum : ans_min;
}
else {
for(int i=0; i<4; i++){
if( cal[i] ){
cal[i]--;
dfs(idx+1,func_cal(idx+1,i,sum));
cal[i]++;
}
}
}
}

int main(){
int TC;
cin >> TC;

for(int tc=1; tc<=TC; tc++){
memset(cal,0,sizeof(cal));
memset(arr,0,sizeof(arr));

ans_max = 2e9 * -1;
ans_min = 2e9;

cin >> n;

for(int i=0; i<4; i++) scanf("%d",cal+i);
for(int i=0; i<n; i++) scanf("%d",arr+i);

dfs(0,arr[0]);
printf("#%d %lld\n",tc, ans_max-ans_min);
}
return 0;
}
``````

• 20분 걸림

## [3] Answer Code (18. 04. 08)

``````#include<iostream>
#include<cstring>
#define inf 1e9
using namespace std;

int n;
int op[5]; // op is operation
int num[13];
int _max, _min;

int cal(int sum, int now_value, int op_idx){
if(op_idx == 1 ) return sum + now_value;
else if( op_idx == 2) return sum - now_value;
else if( op_idx == 3) return sum * now_value;
else return sum / now_value;
}

void dfs(int sum, int idx){
if( idx >= n+1 ){   // [1]
_max = _max < sum ? sum : _max;
_min = _min < sum ? _min : sum;
return ; // [3]
}

for(int i=1; i<=4; i++){    // [2]
if( op[i] > 0 ){
op[i]--;
dfs( cal(sum, num[idx], i) , idx+1);
op[i]++;
}
}
}

int main(){
int tc;
cin >> tc;

for (int i=1; i<=tc; i++) {
_max = -inf;
_min = inf;
cin >> n;

for(int i=1; i<=4; i++)
scanf("%d",op+i);

for(int i=1; i<=n; i++)
scanf("%d",num+i);

dfs(num[1],2);
printf("#%d %d\n", i, _max - _min);
}
return 0;
}

``````

### Review

• 단순 DFS / 30분정도 걸렸다.

• if ([1] )
else ( [2] ) 형태로 하면 [3] 코드가 필요없다.