문제 이해

숫자가 주어지고, 숫자 사이에 (+,-,*,/) 연산 중 하나가 들어갈 수 있다
연산자의 개수는 미리 입력값으로 주어진다.

이 때 나누기에 대한 설명이 여러 가지 나왔지만, JAVA의 기본 나누기 형식을 따른다고 생각하면 좋을 것이다.

이 때, 1 + 2 * 3을 수행할 때 우리가 알고 있는 형식으로 1+ (2 * 3) = 1 + 6 = 7이 아닌 (1 + 2) * 3 = 3 * 3 = 9로 순서대로 계산을 한다.

---

문제 풀이

만약 우리가 알고 있는 우선순위 대로 계산한다면 다른 방법이 존재하겠지만, 처음부터 차례대로 계산해야 하기 때문에 Brute-Force Algorthm을 사용할 수 밖에 없다고 생각했다.

또한 미리 주어진 연산자의 개수 또한 생각해야 한다. Array를 사용하여 0인지 여부를 확인하려 했으나, 어차피 array[0]은 +를 의미한다 등의 추가적인 if문이 필요한 것은 달라질 것이 없으므로 그냥 4개의 variable을 사용하기로 하였다.

마지막으로, 재귀함수를 이용하여 DFS 형식으로 모든 경우를 살펴 보기로 결심하였다.

이유는 Root부터 Leaf까지 모든 Node를 지나는 중간 결과를 알고 있어야 답을 구할 수 있기 때문에 이런 방식을 채택했다.

---

코드

import java.util.*;

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	static int N = 0;
	static ArrayList<Long> numbers = new ArrayList<Long>();
    // numbers : 처음에 주어지는 수열의 값을 저장한 Array

	static int plus, minus, multiple, divide = 0;
    // plus : + 개수, minus : - 개수, multiple : * 개수, divide : / 개수

	static long max = Long.MIN_VALUE; 
	static long min = Long.MAX_VALUE;
    // 결과는 -10억보다 크거나 같고 10억보다 작거나 같으므로 
    // int대신 Long을 활용하였다.

	static void rec_fun(long value, int index) {
        // value : Array에서 k번째 값을 꺼내 계산을 수행하고 싶을 때
        //         k-1번째까지 연산을 수행한 결과값을 의미한다
        // index : 이번 연산에서 사용할 Array 값의 index

        /*
        (ex) 1 + 2 * 3 연산이고, * 3을 계산할 차례의 재귀함수에서 
        value = 1 + 2이고 index는 (1,2,3)이 저장 되어 있는 Array 중 
        3 값을 꺼내야 하므로 index = 2이다.
        */

		if(index==N) {  
        // index = N이라는 것은 모든 Array Element를 확인했다는 의미이므로
        // max값이나 min 값에 들어갈 수 있을지 확인하는 과정을 거친다.
			if(min > value) {
				min = value;
			}
			if(max < value) {
				max = value;
			}
			return;
		}
		
		long num = numbers.get(index);
		if(plus!=0) {
			plus--;
			rec_fun(value+num, index+1);
			plus++; 
            // 재귀함수 하나가 끝난 경우 +가 들어간 Case는 종료되었으므로 
            // 값을 원상복구 시켜줌
		}
		if(minus!=0) {
			minus--;
			rec_fun(value-num, index+1);
			minus++;
		}
		if(multiple!=0) {
			multiple--;
			rec_fun(value*num, index+1);
			multiple++;
		}
		if(divide!=0) {
			divide--;
			rec_fun(value/num, index+1);
			divide++;
		}
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		sc.nextLine();
		String M = sc.nextLine();
		String[] number = M.split(" ");
		for(int i =0;i<N;i++) {
			numbers.add(Long.parseLong(number[i]));
		}
		
		String four = sc.nextLine();
		number = four.split(" ");
		plus = Integer.parseInt(number[0]);
		minus = Integer.parseInt(number[1]);
		multiple = Integer.parseInt(number[2]);
		divide = Integer.parseInt(number[3]);
		
		rec_fun(numbers.get(0), 1);
		
		System.out.println(max);
		System.out.println(min);
	}
}

---

결과