[BOJ]#14888:演算子の挿入

質問する

入力

しゅつりょく

入力例1

入力

しゅつりょく

入力例2

入力

しゅつりょく

入力例3

入力

しゅつりょく

📝 最初の論理

"연산자의 모든 순열을 나열해서 하나하나 계산을 하자!" 

論理的説明

1. 셋째 줄에 입력받은 연산자들의 개수에 따라 인덱스 번호를 나열한다. ('+'는 0, '-'는 1, '*'는 2, '/'는 3)

2. 나열한 값들로 next_permutation을 이용하여 순열을 구한다.

2-1. 순열 하나를 구할 때마다 해당 순서에 맞게 계산한다.

2-2. min, max를 비교하여 갱신한다.

コード#コード#

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int maxResult=-999999999, minResult=999999999;

int calculate(int totalOperators, int onePermuations[], int inputValue[]){
    int total=inputValue[0];
    
	/* step 2-1. */
    
    for(int i=0;i<totalOperators;i++){
       
        if(onePermuations[i]==0){
            total=total+inputValue[i+1];
        }else if(onePermuations[i]==1){
            total=total-inputValue[i+1];
        }else if(onePermuations[i]==2){
            total=total*inputValue[i+1];
        }else if(onePermuations[i]==3){
            if(total<0){
                total*=-1;
                total=(int)(total/inputValue[i+1]);
                total*=-1;
            }
            else total=(int)(total/inputValue[i+1]);
        }
        
    }
  	/* step 2-2. */
    if(total > maxResult) maxResult=total;
    if(total < minResult) minResult=total;

    return 0;
}

int makePermuations (int totalOperators, int operators[], int inputValue[]){
	/* step 1. */
    vector <int> v;
    int onePermutation[totalOperators];
    for(int i=0;i<4;i++){
        for(int j=0;j<operators[i];j++)
        v.push_back(i);
    }
	/* step 2. */
    do{
        for(int i=0;i<totalOperators;i++){
            onePermutation[i]=v[i];
        }
        calculate(totalOperators, onePermutation, inputValue);
    }while(next_permutation(v.begin(), v.end()));

    return 0;
}

int main(){
    int n, a[11], operators[4];
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=0;i<4;i++){
        scanf("%d",&operators[i]);
    }

    makePermuations(n-1, operators, a);

    printf("%d\n%d", maxResult, minResult);
}

❌コード作成時に発生したエラー❌

a[10], operators[3]

if(total > maxResult) maxResult=total;
else if(total < minResult) minResult=total;

📝 2番目の論理

論理的説明

1. 임의의 0으로 초기화 된 연산자 개수만큼의 빈 배열을 만든다. 
(이 배열은 현재 내가 사용하고 있는 연산자의 정보를 나타내는 배열이다. 
예를 들어서 [1,0,1,0] 이면 현재 나는 더하기 하나와 곱하기 하나를 썼다는 뜻이고, 
이 배열에 값을 더해나가는 순서가 연산자가 놓인 위치이다.
만약, [1.0,0,0] 후에 [1,0,1,0] 으로 배열 값이 바꼈다면 더하기를 먼저 사용하고, 그 후에 곱하기를 사용했다는 뜻이다.

2. 1.에서 만든 배열에 반복문을 돌리면서 배열값을 증가시키며 재귀함수를 호출하는데, 연산자 배열과 비교하면서 호출한다.
( 특정 인덱스에 대해 1.에서 만든 임의의 배열값과 연산자 배열값이 같다는 것은 해당 인덱스에 매칭되는 연산자를 다 썼다는 뜻이다.)

2-1. 재귀함수를 호출 할 때 현재 내가 사용한 연산자의 개수, 현재까지의 연산결과, 현재까지의 임의 배열 값들을 넘기면서 호출한다.

2-1-1. 연산을 할 때는 연산 함수를 부르는 시점을 기준으로 방금 사용한 연산자 (실제로는 연산자와 매칭되는 인덱스 값)와, 피연산자, 이때까지의 연산결과를 가지고 진행한다.  
3. 주어진 모든 연산자를 썼으면, 완성된 합계를 가지고 최대값과 최소값을 비교하여 갱신한다.

コード#コード#

#include<stdio.h>
using namespace std;

int n, a[11], operators[4];
int maxResult=-999999999, minResult=999999999;

int calculate(int operatorIndex, int operand, int sum){
    if(operatorIndex==0){
        return sum+operand;
    }else if(operatorIndex==1){
        return sum-operand;
    }else if(operatorIndex==2){
        return sum*operand;
    }else {
        return (int)(sum/operand);
    }
}
void makeOper(int i, int sum, int temp[]){
    
    if(i==n-1){
        if(sum>maxResult) maxResult=sum;
        if(sum<minResult) minResult=sum;
        return;
    }

    for(int j=0;j<4;j++){
      if(temp[j]<operators[j]){
          temp[j]++;
          makeOper(i+1, calculate(j,a[i+1],sum), temp);
          temp[j]--;
      }
    }
    
}

int main(){
    /*input*/
    
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=0;i<4;i++){
        scanf("%d",&operators[i]);
    }

    int temp[4]={0};
    makeOper(0, a[0], temp);

    printf("%d\n%d", maxResult, minResult);
}

❗コード作成時に見逃した❗

戻ると、先ほど使用した配列を解放します.
上のコードでは、makeOpenrを呼び出して再帰し、行に

a[10], operators[3]

タイトルのように、さっき使った配列を解くという意味です.
再帰関数が呼び出されるたびに、更新されたtemp配列が付きます.したがって、戻って戻るときは、その配列を元の状態に戻す必要があります.
そうでない場合、コードは[0,0,0,0]から始まり、すべての演算子を最初に使用したときに終了します.
図に示すように、

上から下まで演算子配列と値は同じであり([2,1,1,1])、配列値の元の状態([2,1,1,0])を返す必要があるが、[2,1,1,1,1,1]の状態を維持する.

整理する