[백준][브루트포스] 14888 연산자 끼워넣기 c++구현

목차

https://www.acmicpc.net/problem/14888

문제

 

코드 구현 방향

나는 범위를 보고 모두 다 할 수 있다고 판단이 들었고 그래서 모든 경우를 구한 뒤 연산을 해주는 방식으로 풀었다.

또한 계산을 할때는 stack을 이용해 연산하였다.

 

 

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;
typedef long long ll;

int T;
int arr[13] = { 0 };
ll Maxsize = -1000000004 , Minsize = 1000000004;

//계산해주는 함수
ll converCacul(ll a, ll b, char c) {
    switch (c)
    {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        if (b == 0) {
            if (a < 0)
                return -1000000000;
            else if (a == 0)
                return  0;
            else
                return 1000000000;
        }
        else
            return a / b;
        break;
    default:
        break;
    }
}

//idx 변환 함수
char converIdx(int idx) {
    switch (idx)
    {
    case 0: return '+';
    case 1: return '-';
    case 2: return '*';
    case 3: return '/';
    default:
        break;
    }
}
ll caculating(string str) {
    stack<ll> q;
    for (int i = T - 1; i >= 0; i--) {
        q.push(arr[i]);
    }
    ll cnt = 0;
    while (q.size() != 1) {
        ll a = q.top();
        q.pop();
        ll b = q.top();
        q.pop();
        ll c = converCacul(a, b, str[cnt]);
        cnt++;
        q.push(c);
    }
    return q.top();
}

//백트래킹을 통해 모든 경우를 구해준다.
void dfs(string str, int oper[4], int num) {
    if (num == T-1) {
        ll k = caculating(str);
        Maxsize = max(Maxsize, k);
        Minsize = min(Minsize, k);
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (oper[i] > 0) {
            oper[i] -= 1;
            num++;
            str += converIdx(i);
            dfs(str, oper, num);
            num--;
            oper[i] += 1;
            str = str.substr(0,str.length() - 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int oper[4] = { 0 };
    string str;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < 4; i++) {
        cin >> oper[i];
    }
    dfs(str, oper, 0);
    cout << Maxsize << "\n";
    cout << Minsize << "\n";
    
    return 0;
}

 

 

더 효율적인 풀이

이건 DAG  알고리즘으로 비순환 그래프이다. 그래서 더 간단하게 풀 수 있다...

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;  
int n;
int a[12], b[4];
int p, minu, mult, divi;
int ret = -1000000001;
int ret2 = 1000000001;
void go(int index, int cur, int plus, int minus, int mul, int div){ 
    //printf("%d\n", index);
    if(index == n - 1){
        ret = max(cur, ret);
        ret2 = min(ret2, cur);
        return; 
    }
    if(plus) go(index + 1, cur  + a[index + 1], plus - 1, minus, mul, div);
    if(minus) go(index + 1, cur - a[index + 1], plus, minus - 1, mul, div);
    if(mul) go(index + 1, cur * a[index + 1], plus, minus, mul - 1, div);
    if(div) go(index + 1, cur / a[index + 1], plus, minus, mul, div - 1);
    return;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){ 
        scanf("%d", &a[i]); 
    }    
    scanf("%d %d %d %d", &p, &minu, &mult, &divi);
    go(0, a[0], p, minu, mult, divi);
    printf("%d\n%d\n", ret,ret2);
    return 0; 
}