[백준 14888][C++] 연산자 끼워넣기 (Silver 1)

[문제보기]

 14888. 연산자 끼워넣기

[풀이과정]

이 문제를 보기 전에 Permutation에 대해서 배웠다 보니 이 문제에 대해 푸는 방향에 대해서 Permutation을 사용하여 

코드를 만들었다. 

입력값을 받을 때 숫자에 대한 입력값은 num배열에 넣고, 연산자에 대한 입력값을 받을때 각 연산에 대한 개수만큼 

vector v에 값을 넣어주는데, +(=0), -(=1), *(=2), /(=3)으로 정하여 넣어주었다.

그리고 v에 넣어진 데이터를 가지고 Permutation을 진행을 하여 숫자를 계산해준다.

 

get_operation(int idx, int x, int y) 함수를 사용하여 연산자에 대한 계산을 진행하는데, x는 이전에 계산된 값이 넣어지고, idx가 연산자의 idx를 의미하고, y가 x에 계산될 숫자를 의미한다. 

 

get_cal()에서는 계산할 숫자와 연산자를 get_operation에 넣어주는 역할을 한다. 

 

위의 로직을 통해 계산된 값을 가지고 Min, Max의 값을 계속 업데이트해준다. 

[소스코드]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int num[11] = {0};
vector<int> v;

long long get_operation(int idx, int x, int y){
    long long sum;

    if(idx == 0){
        sum = x+y;    
    }
    else if(idx == 1){
        sum = x-y;
    }
    else if(idx == 2){
        sum = x*y;
    }
    else{
        sum = x/y;
    }

    return sum;
}

long long get_cal(){
    long long temp = num[0];
    int cnt = 1;
    for(int i=0; i<v.size(); i++){
        temp = get_operation(v[i], temp, num[cnt++]);
    }
    return temp;
}

int main(){
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> num[i];
    }

    for(int i=0; i<4; i++){
        int count;
        cin >> count;
        for(int j=0; j<count; j++){
            v.push_back(i);
        }
    }

    long long Max = -1000000000;
    long long Min = 1000000000;
    do{
        long long temp = get_cal();

        Max = max(Max, temp);
        Min = min(Min, temp);

    }while(next_permutation(v.begin(), v.end()));

    cout << Max << "\n" << Min << "\n";

    return 0;
}

[해결과정 중 실수한 부분]

Max와 Min의 값을 제대로 설정을 못해서 틀렸다고 나왔었다. 이 부분을 10억, -10억으로 고치니깐 바로 

정답이 나왔다.

 

내가 쓴 Permutation을 사용하여 문제를 풀면 간단은 하지만 Permutation으로 나오는 게 중복이 많아서 

실행하는 시간이 길어진다. 그래서 다른 분들은 어떻게 했는지 확인을 해봤는데 dfs를 사용하여 문제를 

푼 분들이 많았다. 

 

---

http://melonicedlatte.com/algorithm/2018/03/18/214856.html

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int oper[4] = {0};
vector<int> num;
vector<int> ans;
vector<int> operation;

int calculator(){
    int sum = num[0];
    for(int i=0; i<n-1; i++){
        int x = operation[i];
        if(x == 0){
            sum += num[i+1];
        }
        else if(x == 1){
            sum -= num[i+1];
        }
        else if(x == 2){
            sum *= num[i+1];
        }
        else{
            sum /= num[i+1];
        }
    }

    return sum;
}

void dfs(int cnt){
    if(cnt == n-1){
        int sum = calculator();
        ans.push_back(sum);
        return;
    }

    for(int i=0; i<4; i++){
        if(oper[i]){
            oper[i]--;
            operation.push_back(i);

            dfs(cnt+1);

            oper[i]++;
            operation.pop_back();
        }
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        num.push_back(x);
    }

    for(int i=0; i<4; i++)
        cin >> oper[i];
    
    dfs(0);

    sort(ans.begin(), ans.end());
    cout << ans.back() << "\n" << ans[0];


}