BOJ - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

• DP + 백트래킹 문제이다.
• 주어진 연산자 횟수를 이용하여 연산자 순서를 정한다
• DP 깊이가 숫자 -1 일 경우 조합된 연산자 순서를 이용하여 최소 값과 최대 값을 갱신한다.
• 아래의 풀이로 연산자 끼워넣기 (2) 통과 할 수 있다(날먹)

 

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int maxSum = Integer.MIN_VALUE;
    private static int minSum = Integer.MAX_VALUE;
    private static char[] operation = new char[]{
            '+', '-', '*', '/'
    };

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int[] numbers = new int[N];
        int[] operations = new int[4];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

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

        dp(0, numbers, operations, "");
        System.out.println(maxSum);
        System.out.println(minSum);
    }

    private static void dp(int depth, int[] numbers, int[] operations, String operationOrder) {
        if (depth == numbers.length - 1) {

            int stack = numbers[0];
            for (int i = 1; i < numbers.length; i++) {
                int number = numbers[i];
                char c = operationOrder.charAt(i - 1);
                if (c == '+') {
                    stack += number;
                } else if (c == '-') {
                    stack -= number;
                } else if (c == '*') {
                    stack *= number;
                } else if (c == '/') {
                    stack = stack / number;
                }
            }

            minSum = Math.min(minSum, stack);
            maxSum = Math.max(maxSum, stack);

            return;
        }

        for (int i = 0; i < operations.length; i++) {
            if (operations[i] == 0) continue;
            operations[i] -= 1;
            dp(depth + 1, numbers, operations, operationOrder + operation[i]);
            operations[i] += 1;
        }
    }

    /**
     * 수식 완성 
     * @param numbers
     * @param operationOrder
     */
    private static void printExpressions(int[] numbers, String operationOrder) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < numbers.length; i++) {
            builder.append(numbers[i]);
            if (i < numbers.length - 1) {
                builder.append(operationOrder.charAt(i));
            }
        }
        System.out.println(builder);
    }
}