[BOJ/Java] 14888: 연산자 끼워넣기

문제

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

N개의 수로 이루어진 수열이 주어진다.

N-1개의 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 사칙연산(덧셈, 뺄셈, 곱셈, 나눗셈)으로 이루어져 있다.

주어진 수의 순서는 바뀌지 않는다. 대신, 연산자를 조합해 수식을 만들 수 있다.

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

• 2 ≤ N ≤ 11
• 수열의 숫자는 1보다 크거나 같고, 100보다 작거나 같다.

 

풀이

처음에 문제를 잘못 읽어서 수의 순서도 조합해야 하는 줄 알고 시간을 버렸다..

그냥 연산자 순열을 만들어서 모든 경우의 수를 계산하여 최댓값, 최솟값을 계산하면 된다.

 

백트래킹으로 모든 연산자를 골라, 연산자 리스트가 완성되면 `calculate` 함수로 식의 결과값을 계산한다. 계산된 값을 현재 `max`, `min` 값과 비교하여 갱신한다. (순열에는 visited 배열이 필요!)

💡 JDK 14버전부터 `break`를 명시하지 않아도 자동으로 분기를 종료하는 `case ->` 문법을 사용할 수 있다. 다만, JDK 14버전 이하에서는 쓸 수 없으므로 알아만 두자.

 

코드

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

public class Main {
    static int n;
    static int[] numbers;
    static List<Character> ops = new ArrayList<>();
    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());
        numbers = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        ops = new ArrayList<>();
        int plus = Integer.parseInt(st.nextToken());
        int minus = Integer.parseInt(st.nextToken());
        int mul = Integer.parseInt(st.nextToken());
        int div = Integer.parseInt(st.nextToken());
        for (int i = 0; i < plus; i++) ops.add('+');
        for (int i = 0; i < minus; i++) ops.add('-');
        for (int i = 0; i < mul; i++) ops.add('*');
        for (int i = 0; i < div; i++) ops.add('/');

        visited = new boolean[n - 1];
        dfs(new ArrayList<>());
        System.out.println(max);
        System.out.println(min);
    }

    // 모든 연산자 순열을 만든다.
    static void dfs(List<Character> selected) {
        // 모든 연산자를 고르면 계산한다.
        if (selected.size() == n - 1) {
            int result = calculate(selected);
            max = Math.max(max, result);
            min = Math.min(min, result);
            return;
        }

        for (int i = 0; i < n - 1; i++) {
            if (!visited[i]) {
                visited[i] = true;
                selected.add(ops.get(i));
                dfs(selected);
                selected.remove(selected.size() - 1);
                visited[i] = false;
            }
        }
    }

    // 식을 계산한다.
    static int calculate(List<Character> ops) {
        int result = numbers[0];
        for (int i = 0; i < ops.size(); i++) {
            int next = numbers[i + 1];
            switch (ops.get(i)) {
                case '+': result += next; break;
                case '-': result -= next; break;
                case '*': result *= next; break;
                case '/': {
                    if (result < 0) {
                        result = -(-result / next);
                    } else {
                        result /= next;
                    }
                    break;
                }
            }
        }
        return result;
    }

}