[백준] 15658 연산자 끼워넣기 (2)

 

간단한 완전탐색 문제다

경우의수가 적기 때문에 연산자가 있는대로 다 넣어보면 된다

 

op배열에 연산자를 넣고 해당연산자가 남아있으면 

수를 줄이고 넣어서 다음 숫자로 넘어가고

다시 수를 처음처럼 늘려준다

 

재귀를 타고 들어가기 때문에 연산한 결과를 계속 가져갔다가

원래대로 돌려준다

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int op[4]; //+,-,x,/;
int a[22],b[22];
int maxn = -1000000005;
int minn = -maxn;
 
void solve(int pos){
    if(pos==n-1){
        maxn = max(maxn,b[pos]);
        minn = min(minn,b[pos]);
        return;
    }
 
    for(int i=0;i<4;i++){
        if(op[i]){
            op[i]--;
            if(i==0) b[pos+1]=b[pos]+a[pos+1];
            else if(i==1) b[pos+1]=b[pos]-a[pos+1];
            else if(i==2) b[pos+1]=b[pos]*a[pos+1];
            else b[pos+1]=b[pos]/a[pos+1];
            solve(pos+1);
            op[i]++;
        }
    }
}
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d",&n);
    for(int i=0;i<n;i++) scanf(" %d",&a[i]);
    for(int i=0;i<4;i++) scanf(" %d",&op[i]);
    b[0]=a[0];
    solve(0);
    printf("%d\n",maxn);
    printf("%d\n",minn);
}