[백준] 14888번 : 연산자 끼워넣기 (JAVA)

인간몽쉘김통통·2023년 11월 23일

DFS 백준 브루트 포스 알고리즘

백준

목록 보기

24/92

문제

이해

입력으로는 수열과 사용할 수 있는 연산자의 개수가 주어진다.

N개의 수열을 입력받으면 N-1개의 연산자를 입력받는다. 각 연산자는 수열의 수 사이에 들어가서 식을 완성한다.

완성된 식은 연산자 우선 순위를 무시하고 연산한다. 따라서, 식에 * 연산이 있더라도 다른 연산자보다 뒤에 있다면 위치대로 연산을 수행한다.

따라서, 위와 같은 식의 결과가 계산된다.

조합가능한 식의 값 중에서 최댓값과 최솟값을 구하여라.

접근

입력받은 수와 연산자 간에는 특별한 관계가 있어보이지 않는다. 따라서, 그리디 알고리즘은 제외.

최댓값과 최솟값을 구하기 위해서는 모든 식의 경우를 탐색해야 할 것으로 보인다. 수의 개수도 최대 11개로 충분히 탐색 가능할 것으로 보인다. 따라서, dfs를 선택한다.

다음으로는 연산자를 배치하는 방법이다.

연산자는 4개의 정수로 입력받는데 각 수는 연산자의 사용가능 횟수이다.

예제 입력 3의 경우에는 2, 1, 1, 1로 '+' 연산자은 2개이며 그 외의 연산자는 1개씩 쓸 수 있다.

식을 완성할 때 이전에 사용했던 연산자는 사용할 수 없기 때문에 사용했던 연산자를 기록하기 위한 배열을 생성해야 한다 (visited[])

dfs는 일반적인 dfs 처럼 N개의 연산자를 배치했다면 현재까지 결과를 저장된 max, min과 비교하여 갱신한다.

코드

package java_baekjoon;

import java.io.*;

public class prob14888 {
    static int N;
    static int[] arr;
    static String[] op_arr;
    static boolean[] visited;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

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

        N = Integer.parseInt(br.readLine());

        String[] input_num = br.readLine().split(" ");
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input_num[i]);
        }

        String[] input_op = br.readLine().split(" ");
        op_arr = new String[N - 1];
        visited = new boolean[N - 1];
        int cnt = 0;

        for (int i = 0; i < Integer.parseInt(input_op[0]); i++) {
            op_arr[cnt++] = "+";
        }
        for (int i = 0; i < Integer.parseInt(input_op[1]); i++) {
            op_arr[cnt++] = "-";
        }
        for (int i = 0; i < Integer.parseInt(input_op[2]); i++) {
            op_arr[cnt++] = "*";
        }
        for (int i = 0; i < Integer.parseInt(input_op[3]); i++) {
            op_arr[cnt++] = "/";
        }

        dfs(arr[0], 0);

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

    static void dfs(int cur, int depth) {
        if (depth == N - 1) {
            max = Math.max(max, cur);
            min = Math.min(min, cur);
            return;
        }

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

            visited[i] = true;
            dfs(cal(op_arr[i], cur, arr[depth + 1]), depth + 1);
            visited[i] = false;
        }
    }

    static int cal(String op, int operand1, int operand2) {
        switch (op.charAt(0)) {
            case '+':
                return operand1 + operand2;
            case '-':
                return operand1 - operand2;
            case '*':
                return operand1 * operand2;
            case '/':
                return operand1 / operand2;
            default:
                return Integer.MAX_VALUE + 1;
        }
    }
}