백 준 - 14888

문제 : www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

문제는 다음과 같습니다.

 

문제에서 요구하는 것은 주어진 수에서 연산자의 위치를 변경함으로써 얻을 수 있는 최대 최소 값을 구하는 것입니다.

핵심은 수는 고정이 되어있고 연산자의 위치를 변경하는 것입니다.

 

따라서 저희는 연산자가 주어지면 이에 대한 갯수를 파악해서 인덱스를 기준으로 순열을 진행하겠습니다.

그렇게 되면 저희는 연산자의 위치를 변경하면서 가능한 모든 경우를 파악하게 되고 이 안에서 최대 및 최소를 구할 수 있게 됩니다.

 

전체적인 코드는 다음과 같습니다

import java.util.*;

public class Main {

    // 문제 14888

    public static int maxValue = -Integer.MAX_VALUE;
    public static int minValue = Integer.MAX_VALUE;



    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int n = stdin.nextInt();

        int[] arr_num = new int[n];
        for (int i = 0 ; i < n ; i++) {

            arr_num[i] = stdin.nextInt();

        }

        int[] arr_cal = new int[4];
        for (int i = 0 ; i < 4 ; i++) {

            arr_cal[i] = stdin.nextInt();
        }

        int[] cals = new int[n-1];

        int idx = 0;

        for(int i = 0 ; i < 4 ; i++) { // 0 = + , 1 = - , 2 = * , 3 = / 으로 생각하기

            for (int j = 0 ; j < arr_cal[i] ; j++) {

                cals[idx] = i;

                idx += 1;
            }
        }

        LinkedList<Integer> values = new LinkedList<>();
        boolean[] flag = new boolean[cals.length];

        permutation(values , flag , arr_num , cals);

        System.out.println(maxValue);
        System.out.println(minValue);

    }

    public static int getValue(int[] arr_num , LinkedList<Integer> values , int[] cals) {

        int val = arr_num[0];

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

            int idx = values.get(i);

            int cal_idx = cals[idx]; //0 -> + , 1 -> - , 2 -> * , 3 -> /

            if (cal_idx == 0 ) {

                val += arr_num[i+1];
            }
            else if (cal_idx == 1) {

                val -= arr_num[i+1];
            }
            else if (cal_idx == 2) {

                val *= arr_num[i+1];
            }
            else {

                val /= arr_num[i+1];
            }
        }

        return val;
    }

    // 위에서 만든 cals의 index 값을 permuation 하면서 연산의 최대 최소 값을 찾는다

    public static void permutation(LinkedList<Integer> values , boolean[] flag , int[] arr_num, int[] cals ) {

        if (isCheck(flag)) {

            int val = getValue(arr_num , values , cals);

            maxValue = Math.max(maxValue , val);
            minValue = Math.min(minValue , val);

        }


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

            if(flag[i] == false) {

                flag[i] = true;
                values.add(i);

                permutation(values , flag, arr_num , cals);

                flag[i] = false;
                values.removeLast();
            }
        }

    }

    public static boolean isCheck(boolean[] flag) {

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

            if (flag[i] == false) {

                return false;
            }
        }

        return true;
    }
}