문제

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

---

입력

첫째 줄에 수의 개수 N가 주어진다.
둘째 줄에는 A1, A2, ..., AN이 주어진다.
셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데,
차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

---

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.

---

풀이

제한조건

• N(2 ≤ N ≤ 11)
• (1 ≤ Ai ≤ 100)

접근방법

완전 탐색
완전 탐색을 통해 계산해도, 연산 수가 많지 않아 충분하다.
완전 탐색을 통해 모든 경우를 계산하고, 그 중 최대 최소를 찾아보자.

백트랙킹, DFS, 순열/조합 생성하기 와 같은 코드를 구현해본적이 있다면 쉬울것이다.

우선 사칙연산을 먼저 쉽게 표현해보자.

	final static int PLUS = 0;
	final static int MINUS = 1;
	final static int MULTIPLY = 2;
	final static int DEVIDE = 3;

알고리즘 문제 풀이시 위와 같이 정의해두면, 조금 더 직관적으로 알 수 있다.

if(value == 0){
...
}else if(value == 1){
...
}

// 위 보다는 아래 형식이 보기 편하다.
if(value == PLUS){
...
}else if(value == MINUS){
...
}

이제 각 연산에 대해서 사용할 수 있다면(개수가 남아있다면) 해당 연산을 적용하고 다음 숫자로 넘어가는것이 반복된다.

동일 작업이 반복적으로 발생하므로 재귀적으로 함수를 구성해서 문제를 풀면 된다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, max, min;
	static int[] arr, oper;

	final static int PLUS = 0;
	final static int MINUS = 1;
	final static int MULTIPLY = 2;
	final static int DEVIDE = 3;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = stoi(in.readLine());

		arr = new int[N];
		String[] inputs = in.readLine().split(" ");
		for (int i = 0; i < N; ++i)
			arr[i] = stoi(inputs[i]);

		oper = new int[4];
		inputs = in.readLine().split(" ");
		for (int i = 0; i < 4; ++i)
			oper[i] = stoi(inputs[i]);

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

		simulation(1, arr[0]);
		System.out.println(max);
		System.out.println(min);
	}

	private static void simulation(int depth, int value) {
		if (depth == N) {
			max = Math.max(max, value);
			min = Math.min(min, value);
			return;
		}
		for (int i = 0; i < 4; ++i) {
			if (oper[i] < 1)
				continue;
			oper[i]--;
			switch (i) {
				case PLUS:
					simulation(depth + 1, value + arr[depth]);
					break;
				case MINUS:
					simulation(depth + 1, value - arr[depth]);
					break;
				case MULTIPLY:
					simulation(depth + 1, value * arr[depth]);
					break;
				case DEVIDE:
					simulation(depth + 1, value / arr[depth]);
					break;
				default:
					break;
			}
			oper[i]++;
		}
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}