연산자 끼워넣기 14888

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

더하기, 빼기, 곱하기, 나누기 연산자를 4개의 배열에 종류별로 개수를 입력으로 받아서 처리가 힘들었는데 변경하니 쉬웠다. 배열에 연산자의 종류를 담도록 해서 해결하였다.

이문제는 순열(순서가 있는 조합)에 해당
숫자개수 N이 11 이 최대이므로 연산자는 10개가 최대이다
최대 O(!10) 으로 생각된다 3628800 이다

근데 실제 횟수 3628800 이다;;

import java.io.*;
import java.util.*;

public class Main
{
    static BufferedReader br;

    static int[] op;//value:  add 0, sub 1, mul 2, div 3

    static int[] arr;
    static int[] nums;
    static int N;

    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    static boolean[] checked;

    public static void main(String[] args) throws IOException
    {
        inputProcess();

        search(0);

        System.out.println(max);
        System.out.println(min);
    }

    public static void inputProcess() throws IOException
    {
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        nums = new int[N];
        arr = new int[N-1];
        op = new int[N-1];
        checked = new boolean[N-1];

        String[] input = br.readLine().split(" ");

        for(int i = 0; i < N; ++i)
        {
            nums[i] = Integer.parseInt(input[i]);
        }

        input = br.readLine().split(" ");

        int[] inputOp = new int[4];
        for(int i = 0; i < 4; ++i)
        {
            inputOp[i] = Integer.parseInt(input[i]);
        }

        int opkind = 0;//value:  add 0, sub 1, mul 2, div 3
        int opcnt = 0;//0 ~ N-1
        while(opcnt < N-1)
        {
            if (inputOp[opkind] > 0)
            {
                op[opcnt] = opkind;
                inputOp[opkind]--;
                opcnt++;
            }
            else
                opkind++;

        }
    }

    public static void search(int depth)
    {
        if(depth == N-1)
        {
            int temp = nums[0];
            for(int i = 0; i < arr.length; ++i)
            {
                if(0 == arr[i])
                    temp += nums[i+1];
                else if(1 == arr[i])
                    temp -= nums[i+1];
                else if(2 == arr[i])
                    temp *= nums[i+1];
                else
                    temp /= nums[i+1];
            }

            max = Math.max(max, temp);
            min = Math.min(min, temp);

            return;
        }

        for(int i = 0; i < N-1; ++i)
        {
            if(false == checked[i])
            {
                arr[depth] = op[i];
                checked[i] = true;
                search(depth+1);
                checked[i] = false;
            }

        }
    }
}