백준 14888번 : 연산자 끼워넣기 java

백준에서 백트래킹 항목에 해당하는 문제는 연산자 끼워넣기입니다.

 

이 문제는 숫자를 몇 개를 입력받을 것인지를 먼저 입력받은 후 그 사이즈만큼 숫자를 입력받으면 됩니다.

 

이 문제에서는 연산자를 '+', '-', '*', '/', 이 4개만 사용하므로 연산자를 저장할 배열은 4개의 공간이 필요할 것입니다.

 

추가 설명은 코드를 보면서 하겠습니다.

 

---

 

import java.util.*;
import java.io.*;

public class Main{
    static int[] num;

    static int N;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        num = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i<N; i++)
            num[i] = Integer.parseInt(st.nextToken());

        int[] calc = new int[4];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<4; i++)
            calc[i] = Integer.parseInt(st.nextToken());

        dfs(num[0], 0, calc);

        System.out.println(max+"\n"+min);
    }

    static void dfs(int sum, int cnt, int[] calc){
        if(cnt == N - 1){
            min = Math.min(min, sum);
            max = Math.max(max, sum);
            return;
        }

        for(int i = 0; i<4; i++){
            if(calc[i] == 0)
                continue;

            int nextSum = sum;

            switch(i){
                case 0:
                    nextSum += num[cnt+1];
                    break;
                case 1:
                    nextSum -= num[cnt+1];
                    break;
                case 2:
                    nextSum *= num[cnt+1];
                    break;
                case 3:
                    nextSum /= num[cnt+1];
                    break;
            }

            calc[i]--;
            dfs(nextSum, cnt+1, calc);
            calc[i]++;
        }
    }
}

 

이 문제에서 숫자들의 순서는 변하지 않습니다.

 

그렇다면 우리는 연산자들만 이동시켜주면서 앞에서부터 연산을 진행하면 됩니다.

 

이를 위하여 숫자의 배열은 main 밖에 선언하여 dfs함수로 재귀할 때 매개변수로 받지 않아도 되게 만들었습니다.

-> 숫자들의 순서는 변하지 않기 때문에 배열의 변화가 없어 이렇게 했습니다.

 

연산자들은 4가지의 종류만 있고 들어오는 순서도 이미 정해져 있기 때문에 int의 배열로 갯수를 입력받았습니다.

->char[]로 선언해서 구현하더라도 switch문을 이용하는데 전혀 지장이 없습니다.

 

dfs 함수는 calc 배열을 매개변수로 받아 변화된 배열을 재귀할 때 넘겨주고 cnt 변수로 지금이 몇 번째 재귀인지를     알 수 있게 했으며 nextSum으로 지금까지의 연산 결과를 저장하여 전역 변수인 max, min과 비교하게 만들었습니다.