[JAVA] 백준- 연산자 끼워 넣기 14888

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

중복된 연산자에 대해서 따로 처리를 해야하는가 생각했는데, 중복계산해도 경우의 수가 10! 밖에 안되서  전체 순열 탐색으로 돌렸더니 통과되었다.

 

import java.util.Scanner;

class Main{
    static int n;
    static int[] nums;
    static int[] operators;
    static int max = -987654321;
    static int min = 987654321;

    static public void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        nums = new int[n];
        operators = new int[n-1];
        for(int i=0;i<n;i++) nums[i] = sc.nextInt();
        int idx = 0;
        for(int i=0;i<4;i++){
            int temp = sc.nextInt();
            for(int j=0;j<temp;j++){
                operators[idx++] = i;
            }
        }

        // 0:+, 1:- 2:* 3:/
        boolean[] visited = new boolean[n-1];
        int[] results = new int[n-1];

        dfs(results,0,visited);

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

    }

    static void dfs(int[] results,int idx,boolean[] visited){
        if(idx == results.length){
            int sum = nums[0];
            for(int i=0;i<results.length;i++){
                if(results[i]==0){ // add
                    sum += nums[i+1];
                }else if(results[i]==1){ // sub
                    sum -= nums[i+1];
                }else if(results[i]==2){ // mul
                    sum *= nums[i+1];
                }else{ // div
                    sum /= nums[i+1];
                }
            }
            max = sum > max ?sum : max;
            min = sum < min ?sum : min;
        }else{
            for(int i=0;i<operators.length;i++){
                if(visited[i]) continue;

                visited[i] = true;
                results[idx] = operators[i];
                dfs(results,idx+1,visited);
                visited[i] = false;
            }
        }
    }

}