[Algorithm] 삼성전자 코딩테스트 - 연산자 끼워넣기(c++)

여러가지 풀이 방법이 있겠지만, 글쓴이는 조합을 활용해서 문제를 풀었다.

벡터에 사용되는 연산자의 개수만큼 해당 연산자의 idx값을 넣어주었다. ex) 1 1 0 1 -> [0, 1, 3] / 2 0 0 2 -> [0, 0, 3, 3]

그리고 조합(next_permuation사용)을 통해 계산을 하고 최소, 최대값을 갱신해주었다.

 

 

코드 첨부

// 연산자 끼워넣기
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
 
int n, m, l;
vector<int> v;
vector<int> op;
char OP[4] = {'+', '-', '*', '/'};
int ans_min = INT_MAX;
int ans_max = -INT_MAX;
 
void cal()
{
    int total = v[0];
    for(int i=1; i<v.size(); i++){
        int a = v[i];
        int idx = op[i-1];
 
        if(OP[idx]=='+'){
            total += a;
        }else if(OP[idx]=='-'){
            total -= a;
        }else if(OP[idx]=='*'){
            total *= a;
        }else if(OP[idx]=='/'){
            total /= a;
        }
    }
 
    ans_min = min(ans_min, total);
    ans_max = max(ans_max, total);
}
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>m;
        v.push_back(m);
    }
 
    for(int i=0; i<4; i++){
        cin>>l;
        for(int j=0; j<l; j++){
            op.push_back(i);
        }
    }
 
    do{
        cal();
    }while(next_permutation(op.begin(), op.end()));
 
    cout<<ans_max<<"\n";
    cout<<ans_min<<"\n";
 
    return 0;
}

 

문제 첨부

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

github첨부

github.com/jungahshin/algorithm/blob/master/c:c%2B%2B/14888_review_2.cpp

jungahshin/algorithm