BOJ14888 연산자 끼워넣기

https://www.acmicpc.net/problem/14888 (opens new window)

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다.

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구한다.

백트래킹

backtracking (opens new window)

private static void backtracking(int depth, int result) {
    if (depth == n) { // (6)
        max = Math.max(max, result);
        min = Math.min(min, result);
        return;
    }

    for (String key : operators.keySet()) { // (1)
        if (operators.get(key) > 0) { // (2)
            operators.put(key, operators.get(key) - 1); // (3)
            switch (key) { // (4)
                case "+":
                    backtracking(depth + 1, result + numbers[depth]);
                    break;
                case "-":
                    backtracking(depth + 1, result - numbers[depth]);
                    break;
                case "*":
                    backtracking(depth + 1, result * numbers[depth]);
                    break;
                case "/":
                    backtracking(depth + 1, result / numbers[depth]);
                    break;
            }
            operators.put(key, operators.get(key) + 1); // (5)
        }
    }
}

(1) map에 저장된 연산자를 탐색 및 사용하기 위한 반복문이다.
(2) 연산자의 개수가 0개 이상일 때만 사용이 가능하다.
(3) 연산을 위해 연산자의 개수를 차감한다.
(4) 해당 연산자의 연산을 진행한다.
(5) 연산이 완료되면 모든 조합을 시도하기 위해 연산자의 개수를 원상복귀 시킨다.
(6) depth == n이면 모든 연산이 완료된 것이기 때문에 max와 min을 최신화 한다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BOJ14888 {

    private static int n;
    private static int[] numbers;
    private static int max = Integer.MIN_VALUE;
    private static int min = Integer.MAX_VALUE;
    private static Map<String, Integer> operators = new HashMap<>();

    private static void backtracking(int depth, int result) {
        if (depth == n) {
            max = Math.max(max, result);
            min = Math.min(min, result);
            return;
        }

        for (String key : operators.keySet()) {
            if (operators.get(key) > 0) {
                operators.put(key, operators.get(key) - 1);
                switch (key) {
                    case "+":
                        backtracking(depth + 1, result + numbers[depth]);
                        break;
                    case "-":
                        backtracking(depth + 1, result - numbers[depth]);
                        break;
                    case "*":
                        backtracking(depth + 1, result * numbers[depth]);
                        break;
                    case "/":
                        backtracking(depth + 1, result / numbers[depth]);
                        break;
                }
                operators.put(key, operators.get(key) + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt(); // 수의 개수 2 <= n <= 11
        numbers = new int[n];

        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }

        operators.put("+", scanner.nextInt());
        operators.put("-", scanner.nextInt());
        operators.put("*", scanner.nextInt());
        operators.put("/", scanner.nextInt());

        backtracking(1, numbers[0]);

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

#BOJ #브루트포스 알고리즘 #백트래킹