Gidhub BE Developer

[BOJ] 14888. 연산자 끼워넣기

2018-10-05
goodGid

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로 초기화하는 실수를 했다.


Comments

Content