[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개의 결과를 계산해보면 아래와 같다.

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

 

#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;
}