백준 14888 연산자 끼워넣기(JAVA)

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

14888번: 연산자 끼워넣기

 

 

 

풀이)

import java.util.Scanner;

public class Main_BJ_14888_연산자끼워넣기 {
    static int[] operator = new int[4]; //+ - * /
    static int[] arr;
    static int n, max, min;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();
        for(int i=0; i<4; i++)
            operator[i] = sc.nextInt();

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;
        result(arr[0], 1);
        System.out.println(max);
        System.out.println(min);


    }//main
    private static void result(int num, int idx){
        if(idx == n){
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }
        for(int i=0; i<4; i++){
            if(operator[i] >0){
                operator[i]--;
                switch (i){
                    case 0:
                        result(num+arr[idx], idx+1);
                        break;
                    case 1:
                        result(num-arr[idx], idx+1);
                        break;
                    case 2:
                        result(num*arr[idx], idx+1);
                        break;
                    case 3:
                        result(num/arr[idx], idx+1);
                        break;
                }
                operator[i]++;
            }
        }
    }//result
}

순열을 이용해서 다 뽑아도 된다!!

 

순열을 이용한다면...

import java.util.ArrayList;
import java.util.Scanner;

public class Main_BJ_14888_연산자끼워넣기2 {
    static int[] operator = new int[4]; //+ - * /
    static int[] arr, cal;
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean[] visited;
    static int n, max, min;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();
        for(int i=0; i<4; i++) {
            operator[i] = sc.nextInt();
            while(operator[i]>0){
                list.add(i);
                operator[i]--;
            }

        }

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;
        visited = new boolean[n-1];
        cal = new int[n-1];
        result( 0);

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


    }//main
    private static void result(int idx){
        if(idx == n-1){
            int num = calculate();

            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }

        for(int i=0; i<n-1; i++){
            if(visited[i])
                continue;

            visited[i] = true;
            cal[idx] = list.get(i);
            result(idx+1);
            visited[i] = false;
        }
    }//result
    private static int calculate(){
        int num = arr[0];
        for(int i=0; i<n-1; i++){
            switch (cal[i]){
                case 0:
                    num += arr[i+1];
                    break;
                case 1:    // -
                    num -= arr[i+1];
                    break;
                case 2:    // *
                    num *= arr[i+1];
                    break;
                case 3:    // /
                    num /= arr[i+1];
                    break;
            }
        }
        return num;
    }//calculate
}

일단, scanner를 사용했으므로 조금 느리지만, 첫 번째 경우가 좀 더 적게 걸린다(당연할듯...)