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

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

---

dfs 알고리즘을 이용해서 문제를 풀었다.

N-1 개의 연산자가 주어지므로 깊이가 N-1 인 그래프를 탐색한다는 생각으로 풀었다.

수열은 연속된 수이므로 처음 수만 알면 N 번째 수는 뭔지 몰라도 된다.

dfs 알고리즘을 보자.

    public static void dfs(int depth, int sum) {
    	// 연산자를 다 골랐으면 종료하며 최대값 최소값 업데이트
        if (depth == N - 1) {
            MAX = Math.max(MAX, sum);
            MIN = Math.min(MIN, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            // 남은 연산자가 있다면
            if (0 < calArr[i]) {
                calArr[i]--;
                // 더하기
                if (i == 0) {
                    dfs(depth + 1, sum + arr[depth + 1]);
                } else if (i == 1) {
                    dfs(depth + 1, sum - arr[depth + 1]);
                } else if (i == 2) {
                    dfs(depth + 1, sum * arr[depth + 1]);
                } else {
                    dfs(depth + 1, sum / arr[depth + 1]);
                }
                calArr[i]++;
            }
        }
    }

일단 종료 조건은 깊이가 N-1 이 되면 종료한다. 즉, 연산자를 N-1 개 골랐으면 다 골랐으므로 완성된 수열의 계산식의 답을 보고 최대값 최소값과 비교하여 업데이트한다.

일단 처음 시작은 depth = 0, sum = 수열의 처음 수 이다.
연산자 배열을 0번째(+)부터 남은 연산자가 있는지 본다.
연산자를 하나 사용할 것이므로 사용한 연산자의 위치의 배열의 수를 -1 해준다.

각 연산자에 따라 다음 dfs 로 넘겨주는 sum 을 업데이트하여서 넘겨준다. 또한 연산자를 하나 골랐으므로 depth + 1 을 넘겨준다.

위의 연산자를 고른 경우가 끝난 경우 다시 사용한 연산자를 반납해줘야 하므로 즉, 다른 연산자를 쓰는 경우로 바뀌면 연산자의 수를 전으로 돌려야 하므로 마지막에 calArr[i]++; 을 해주어 수를 맞춰준다.

모든 경우를 탐색하여 MAX 와 MIN 을 찾고 출력한다.

---

public class bj14888 {

    private static int N, MAX = -1000000000, MIN = 1000000000;
    public static int[] arr;
    public static int[] calArr = new int[4];

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        String line = br.readLine();
        String[] split = line.split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }

        line = br.readLine();
        split = line.split(" ");
        for (int i = 0; i < 4; i++) {
            calArr[i] = Integer.parseInt(split[i]);
        }

        dfs(0, arr[0]);

        bw.write(MAX + "\n" + MIN);

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int depth, int sum) {
        if (depth == N - 1) {
            MAX = Math.max(MAX, sum);
            MIN = Math.min(MIN, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            // 남은 연산자가 있다면
            if (0 < calArr[i]) {
                calArr[i]--;
                // 더하기
                if (i == 0) {
                    dfs(depth + 1, sum + arr[depth + 1]);
                } else if (i == 1) {
                    dfs(depth + 1, sum - arr[depth + 1]);
                } else if (i == 2) {
                    dfs(depth + 1, sum * arr[depth + 1]);
                } else {
                    dfs(depth + 1, sum / arr[depth + 1]);
                }
                calArr[i]++;
            }
        }
    }
}