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;
}

Review

  • 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;
}

Review

  • 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] 코드가 필요없다.


Comments

Content