백준|14888번|연산자 끼워넣기

문제설명
N개의 숫자로 이루어진 수열과 수와 수 사이에 끼워넣을 수 있는 연산자 N-1개를 입력받고 수식을 만들었을 때 구할 수 있는 최대값과 최소값을 구하는 문제입니다.(연산은 +, -, X, / 상관하지않고 앞에서부터 수행합니다.)

작동 순서
1. 수열의 개수 N을 입력받습니다.
2. 수열을 입력받습니다.
3. 연산자의 종류별 개수를 입력받습니다.
4. 수열 1번을 기본값으로 두고 2번부터 연산을 시작합니다.(해당 연산의 개수가 남아있으면 해당 연산을 수행)
5. 모든 연산을 끝낸 뒤의 값을 비교해가며 최소값과 최대값을 구합니다.
6. 최소값과 최대값을 출력합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Calculate{
    int plus, minus, mul, div, index, sum;
    Calculate(int plus, int minus, int mul, int div, int index, int sum){
        this.plus=plus;
        this.minus=minus;
        this.mul=mul;
        this.div=div;
        this.index=index;
        this.sum=sum;
    }
}

public class 백준_14888번_연산자끼워넣기 {
    static Calculate search(Queue<Calculate> q, int[] num){
        Calculate c = q.poll();
        if(c.plus>=1){
            q.add(new Calculate(c.plus-1,c.minus,c.mul,c.div,c.index+1,c.sum+num[c.index]));
        }
        if(c.minus>=1){
            q.add(new Calculate(c.plus,c.minus-1,c.mul,c.div,c.index+1,c.sum-num[c.index]));
        }
        if(c.mul>=1){
            q.add(new Calculate(c.plus,c.minus,c.mul-1,c.div,c.index+1,c.sum*num[c.index]));
        }
        if(c.div>=1){
            q.add(new Calculate(c.plus,c.minus,c.mul,c.div-1,c.index+1,c.sum/num[c.index]));
        }
        return c;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int maxCalc = -1000000000;
        int minCalc = 1000000000;
        int[] num = new int[N];
        int[] operator = new int[4];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) num[i]=Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<4;i++) operator[i]=Integer.parseInt(st.nextToken());

        Queue<Calculate> q = new LinkedList<>();
        q.add(new Calculate(operator[0], operator[1], operator[2], operator[3],1,num[0]));

        while(!q.isEmpty()){
            Calculate c = search(q, num);
            if(c.index==N) {
                if (c.sum > maxCalc) maxCalc = c.sum;
                if (c.sum < minCalc) minCalc = c.sum;
            }
        }
        System.out.printf("%d\n%d", maxCalc, minCalc);
    }
}