[BOJ] 14888 연산자 끼워넣기 (Java)

문제 링크

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

 

문제 이해

일반적인 재귀 문제였다. 

주어진 수의 순서를 바꾸면 안 된다는 조건이 있어서 어렵지 않았다!

그냥 재귀의 종료 조건을 배열의 순서가 다 지나면 끝내고,

숫자가 남아있으면 재귀 호출하면 간단하게 풀리는 문제!

 

코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_14888_연산자끼워넣기 {

    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;

    static int arraySize;
    static int [] array;

    static int max;
    static int min;

    public static void calculation(int plus, int minus, int multi, int divide, int index, int answer) {
        // 종료
        if (index == arraySize) {
            min = Math.min(min, answer);
            max = Math.max(max, answer);
            return;
        }
        if (plus > 0) {
            calculation(plus - 1, minus, multi, divide, index + 1, answer + array[index]);
        }
        if (minus > 0) {
            calculation(plus, minus - 1, multi, divide , index + 1,answer - array[index]);
        }
        if (multi > 0) {
            calculation(plus, minus, multi - 1, divide, index + 1, answer * array[index]);
        }
        if (divide > 0) {
            calculation(plus, minus, multi, divide - 1, index + 1, answer / array[index]);
        }
    }


    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        arraySize = Integer.parseInt(br.readLine().trim());
        array = new int[arraySize];

        st = new StringTokenizer(br.readLine().trim());
        for (int idx = 0; idx < arraySize; idx++) {
            array[idx] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine().trim());
        int plus = Integer.parseInt(st.nextToken());
        int minus = Integer.parseInt(st.nextToken());
        int multi = Integer.parseInt(st.nextToken());
        int divide = Integer.parseInt(st.nextToken());

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

        calculation(plus, minus, multi, divide, 1, array[0]);

        sb.append(max).append("\n");
        sb.append(min).append("\n");
        System.out.println(sb.toString());
    }
}