[algorithm] 백준 - 연산자 끼워넣기 & 연산자 끼워넣기 2

4분기로 나누는 방법과 1분기로 가는 방법이 있다.
https://book.algospot.com/estimation.html
이것은 연산 개수 당 걸리는 시간에 대한 자료이니 참고하는 것이 좋다.

알고리즘 문제 해결 전략

연산자 끼워넣기 문제에서, 10!로 1분기의 경우 1.3초가 걸렸다.
4분기는 O(4^n)으로 0ms가 걸렸다.

따라서 1분기도 가능하지만 4분기가 좋다.

연산자 끼워넣기(2) 문제는 1분기로 하게 되면, 44P10으로 연산량이 많아 시간초과가 난다.
따라서 4분기로 나누면 O(4^n)으로 0ms가 걸린다.

1분기

// 연산자 끼워넣기
#include <iostream>
#include <vector>
using namespace std;

char operatorArray[] = {'+', '-', '*', '/'};
vector<int> numVector;
bool selected[11] = {false};
long long maxNum = -9876543210;
long long minNum = 9876543210;
void permutation(int index,vector<char> realOperatorVector, vector<char> operatorVector){
    if(index == realOperatorVector.size()){
        long long sum = numVector[0];
        for(int i = 1; i < numVector.size(); i++){
            if(operatorVector[i - 1] == '+'){
                sum += numVector[i];
            }
            else if(operatorVector[i - 1] == '-'){
                sum -= numVector[i];
            }
            else if(operatorVector[i - 1] == '*'){
                sum *= numVector[i];
            }
            else{
                sum /= numVector[i];
            }
        }
        if(maxNum < sum) maxNum = sum;
        if(minNum > sum) minNum = sum;

        return;
    }
    for(int i = 0; i < realOperatorVector.size(); i++){
        if(selected[i]) continue;
        selected[i] = true;
        operatorVector.push_back(realOperatorVector[i]);
        permutation(index + 1, realOperatorVector, operatorVector);
        operatorVector.pop_back();
        selected[i] = false;
    }
}
int main(void){
    int count, num, operatorCount;
    vector<char> realOperatorVector, operatorVector;
    cin >> count;
    for(int i = 0; i < count; i++){
        cin >> num;
        numVector.push_back(num);
    }
    for(int i = 0; i < 4; i++){
        cin >> operatorCount;
        while(operatorCount--){
            realOperatorVector.push_back(operatorArray[i]);
        }
    }
    permutation(0, realOperatorVector, operatorVector);
    cout << maxNum << "\n" << minNum;
    
}

 

4분기

// 연산자 끼워넣기(2)
#include <iostream>
#include <vector>
using namespace std;

vector<int> numVector;
bool selected[11] = {false};
long long maxNum = -9876543210;
long long minNum = 9876543210;
void permutation(int index, int size, int plusCount, int minusCount, int multipleCount, int divideCount, long long sum){
   if(index == size){
        maxNum = max(maxNum, sum);
        minNum = min(minNum, sum);
        return;
    }
        if(plusCount != 0) permutation(index + 1, size, plusCount - 1,minusCount, multipleCount, divideCount, sum + numVector[index + 1]);
        if(minusCount != 0) permutation(index + 1, size, plusCount,minusCount - 1, multipleCount, divideCount, sum - numVector[index + 1]);
        if(multipleCount != 0) permutation(index + 1, size, plusCount,minusCount, multipleCount - 1, divideCount, sum * numVector[index + 1]);
        if(divideCount != 0) permutation(index + 1, size, plusCount,minusCount, multipleCount, divideCount - 1, sum / numVector[index + 1]);
}
int main(void){
    vector<int> operatorVector;
    int count, num;
    cin >> count;
    for(int i = 0; i < count; i++){
        cin >> num;
        numVector.push_back(num);
    }
    for(int i = 0; i < 4; i++){
        cin >> num;
        operatorVector.push_back(num);
    }
    permutation(0,count - 1,operatorVector[0],operatorVector[1],operatorVector[2],operatorVector[3], numVector[0]);
    cout << maxNum << "\n" << minNum;
    
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102906.cpp

jeongdaeun98/algorithm

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102907.cpp

jeongdaeun98/algorithm