[14888] 연산자 끼워넣기

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

N개의 수로 이루어진 수열과

+, -, *, / 의 연산자 개수가 주어졌을 때

수 사이에 사용할 수 있는 연산자를 넣어보고

식의 결과 최대 값과 최소 값을 찾는 문제이다.

특이한 점은 연산은 *, / 먼저 하는게 아니라 왼쪽에서 오른쪽으로 순서대로 진행한다.

수열의 길이는 최대 10이므로 완탐을 해주면 된다.

백트레킹을 활용해 연산자를 n-1개 선택하고

계산 후 최대 값과 최소 값을 갱신하면 된다.

남아있는 연산자가 없는 경우 현재 연산자를 선택하면 안되고

사용 후 되돌려 놓을 땐 연산자 개수를 다시 올려 놓아야 한다.

이 문제의 함정아닌 함정은 범위이다. 10^-9 ~ 10^9 이므로

처음 max값과 min값을 초기화할 때 주의해야 한다.

max값을 0 min 값을 987654321 이런식으로 하면 나 처럼 틀린다.

끝.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, maxi, mini;
int arr[11], op[5];
int visit[11];
void func(int num){
    if(num == n){
        int ret = arr[0];
        for(int i=1; i<n; i++){
            int d = visit[i];
            if(d==1){
                ret += arr[i];
            }else if (d==2){
                ret -= arr[i];
            }else if (d==3){
                ret *= arr[i];
            }else if (d==4){
                ret /= arr[i];
            }
        }
 
        maxi = max(maxi, ret);
        mini = min(mini, ret);
 
        return ;
    }
    for(int i=1; i<=4; i++){
        if(op[i]){
            visit[num] = i;
            op[i]--;
            func(num+1);
            op[i]++;
            visit[num] = 0;
        }
    }
}
 
 
int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", arr+i);
    }
    for(int i=1; i<=4; i++){
        scanf("%d", op+i);
    }
 
    maxi = -1000000001;
    mini = 1000000001;
 
    func(1);
 
    printf("%d\n%d\n", maxi, mini);
 
    return 0;
}