[BOJ] 연산자 끼워넣기

[문제]

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

14888번: 연산자 끼워넣기

 

[풀이]

1) 조합으로 해결

 

2)

decideOp=> 연산자 조합 생성 

 

현재까지 구한 연산자들의 개수 (cnt) 가 N-1 이면 계산을 시작한다. 

 

3) calc에서는 chk에 담아온 연산자의 인덱스와 맞게 계산을 진행한다. 

연산자의 우선순위에 관계없이 앞에서부터 계산하기 때문에 중간 연산 결과 저장 변수인 res에는 num[0]을 저장한다.

(최대, 최소값 비교)

 

4) chk[] (<- 연산자 조합 저장 배열) 에 맞게 연산을 진행한다. 

문제 본문에 적힌 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

나눗셈은 조건을 걸어줘야 한다. 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

#include <iostream> #include <vector>   using namespace std; int op[12], order[12]; int chk[12]; int nums[12]; int n, minn= 1000000001, maxx = -1000000001; int min(const int &a, const int &b) {     if (a > b ) return b;     return a; } int max(const int &a, const int &b) {     if (a > b ) return a;     return b; } void calc() {     int idx = 0;     int res = nums[0];            for (int i = 1; i < n; i++) {         switch(chk[idx]) {             case 1:             res += nums[i];             break;             case 2 :             res -= nums[i];             break;             case 3 :             res *= nums[i];             break;             case 4:{             if (res < 0 ) {                 res = -(abs(res)/nums[i]);             }             else res /= nums[i];             break;             }         }         idx++;     }     minn = min(minn, res);     maxx = max(maxx, res); } void decideOp(int cnt) {     if (cnt == n-1) {         //수의 개수 -1개만큼 정한다.         calc();         return;     }       for (int i = 0; i < 4; i++) {         if (op[i] > 0) {             chk[cnt] = i+1;             op[i]--;             decideOp(cnt+1);             op[i]++;         }     } } int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n;     for (int i= 0; i < n; i++) {         cin >> nums[i];     }       for (int i = 0; i < 4; i++) {         cin >> op[i];     }       decideOp(0);       cout << maxx << '\n' << minn << '\n';     return 0; }

 

[next_permutation 사용 버전 ]

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
 
//풀이 24분 
 
using namespace std;
 
int n, nums[12], op_num[4];
vector<int> op;
 
int calc(int a, int b, int op) {
    switch (op)
    {
    case 0:
        //+
        return a+b;
    case 1:
    //-
    return a-b;
    case 2:
    //*
    return a*b;
    case 3:
    if (a < 0)  {
        a = -a;
    int tmp = a / b;
    return -tmp;
    }
    else return a/b;    
    }
    return 0;
 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    for (int i = 0; i < 4; i++) {
        int tmp;
        cin >> tmp;
        op_num[i] = tmp;
 
        for (int j = 0; j < tmp; j++) {
             op.push_back(i);
        }  
    }
    //input 
 
 
        int max_res = INT_MIN, min_res=INT_MAX;
        do {
 
            int res = nums[0], op_idx = 0;
            for (int i = 1; i < n && op_idx < n-1; i++, op_idx++) {
                // cout << op[op_idx] << '\n';
                res = calc(res, nums[i], op[op_idx] );
                // cout <<"result = " <<  res << '\n';
            }
            max_res = max(max_res, res);
            min_res = min(min_res, res);
            // cout << '\n';
        } while(next_permutation(op.begin(), op.end()));
        
        cout << max_res << '\n' << min_res << '\n';
    
    return 0;
}