백준 14888 - 연산자 끼워넣기

DFS 조합 + 시뮬레이션 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    static int N;
    static int[] map;
    static int[] operation;
    static boolean[] visited;
    static int[] oper;
    static int resultMax = -98765432;
    static int resultMin = 98765432;
    static LinkedList<Integer> list = new LinkedList();

    public static void main(String[] args){

        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        map = new int[N];

        for(int i=0; i<N; i++){
            map[i] = scanner.nextInt();
        }

        oper = new int[N-1];
        operation = new int[4];
        for(int i=0; i<4; i++){
            operation[i] = scanner.nextInt();
        }

        operationConveter();

        visited = new boolean[oper.length];

        DFS(0);

        System.out.println(resultMax);
        System.out.println(resultMin);
    }

    static void DFS(int depth){

        if(depth == N-1){
            calculater();
            return;
        }

        for(int i=0; i<visited.length; i++){
            if(visited[i] == false){
                visited[i] = true;
                list.add(oper[i]);
                DFS( depth+1);
                 list.removeLast();
                visited[i] = false;
            }
        }

    }

    static void operationConveter(){
        int count=0;
        for(int i=0; i<operation[0]; i++){
            oper[count] = 0;
            count++;
        }

        for(int i=0; i<operation[1]; i++){
            oper[count] = 1;
            count++;
        }

        for(int i=0; i<operation[2]; i++){
            oper[count] = 2;
            count++;
        }

        for(int i=0; i<operation[3]; i++){
            oper[count] = 3;
            count++;
        }


    }

    // 숫자가 맞는지 compare
    static int compare(){

        int[] temp = new int[4];
        int flag = 0;

        for(int i=0; i<4; i++){
            temp[i] = 0;
        }

        for(int i=0; i<list.size(); i++){

            if(list.get(i) == 0){
                temp[0] += 1;
            }

            if(list.get(i) == 1){
                temp[1] += 1;
            }

            if(list.get(i) == 2){
                temp[2] += 1;
            }

            if (list.get(i) == 3){
                temp[3] += 1;
            }

        }

        for(int i=0; i<operation.length; i++){

            if(operation[i] == temp[i]){
                continue;
            }

            if(operation[i] != temp[i]){
                flag = 9999;
            }

        }
        return flag;
    }

    static void calculater(){

        int temp = 0;

        for(int i=0; i<N-1; i++){

            if(i==0){

                if(list.get(i) == 0){
                    temp += map[i] + map[i+1];
                }

                if(list.get(i) == 1){
                    temp += map[i] - map[i+1];
                }

                if(list.get(i) == 2){
                    temp += map[i] * map[i+1];
                }

                if(list.get(i) == 3){
                    temp += map[i] / map[i+1];
                }

                continue;
            }

            if(list.get(i) == 0){
                temp = temp + map[i+1];
            }

            if(list.get(i) == 1){
                temp = temp - map[i+1];
            }

            if(list.get(i) == 2){
                temp = temp * map[i+1];
            }

            if(list.get(i) == 3){
                temp = temp / map[i+1];
            }

        }

        resultMax = Math.max(temp, resultMax);
        resultMin = Math.min(temp, resultMin);
    }
}