링크

연산자 끼워넣기

문제

풀이

이 문제는 나눌 때 주의해야 한다. 음수를 양수로 나눌때 음수값을 양수로 바꾸고 계산 후 다시 음수로 변경해줘야 한다.

그리고 부호를 백트래킹을 통해 모든 조합을 계산하여 최솟값과 최댓값을 계산하도록 했다.

변수

    public static List<String> list = new ArrayList<>();
    public static String[] arr = null;
    public static boolean[] visited = null;
    public static long min = Long.MAX_VALUE;
    public static long max = Long.MIN_VALUE;
    
        public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = br.readLine().split(" ");
        String[] buho = br.readLine().split(" "); // 플, 마, 곱, 나
        List<String> buhos = new ArrayList<>();

전역변수에는 list(연산의 조합), arr(연산할 숫자들), visited(부호를 조합할때 방문했는지 체크), min, max(각각 최댓값과 최솟값을 저장할 변수)로 이루어져 있다.

main함수에는 arr, buho(순서대로 플러스, 마이너스, 곱셈, 나눗셈)이 있고 buhos는 각각 몇번씩 연산들을 사용할 것인지를 저장한다
예를들어 buho가 2 1 1 1 이면 buhos에는 {+, +, -, *, /}가 들어가게 된다.

값 설정하기

        for(int i=0;i<buho.length;i++){
            String element = "";
            if(i == 0) element = "+";
            else if(i == 1) element = "-";
            else if(i == 2) element = "*";
            else if(i == 3) element = "/";
            for(int j=0;j<Integer.parseInt(buho[i]);j++){
                buhos.add(element);
            }
        }

        visited = new boolean[buhos.size()];
        dfs(0, buhos);

buho에 횟수만큼 buhos를 만든다. 그리고 dfs를 사용하여 모든 연산의 조합을 셋팅한다.

dfs

public static void dfs(int start, List<String> buhos){
        if(list.size() == visited.length){
            int result = Integer.parseInt(arr[0]);

            for(int i=0;i<list.size();i++){
                int elementNum = Integer.parseInt(arr[i+1]);
                String elementBuho = list.get(i);

                if(elementBuho.equals("+")){
                    result += elementNum;
                } else if(elementBuho.equals("-")){
                    result -= elementNum;
                } else if(elementBuho.equals("*")){
                    result *= elementNum;
                } else if(elementBuho.equals("/")){
                    if(result < 0 && elementNum > 0){
                        result = (int)(Math.abs(result) / elementNum);
                        result *= -1;
                    } else{
                        result = (int)(result / elementNum);
                    }
                }
            }

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

            return;
        }

        for(int i=0;i< visited.length;i++){
            if(!visited[i]){
                visited[i] = true;
                list.add(buhos.get(i));
                dfs(0, buhos);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }

dfs를 통해 모든 연산의 조합을 찾아서 연산한 뒤 max값과 min값을 설정해준다.