import sys
N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
operators = list(map(int, sys.stdin.readline().split()))
case = ['+', '-', '*', '//']
result = []
def dfs(current_value, next_index, operator, operator_list):
if operator == "+":
current_value += numbers[next_index]
operator_list[0] -= 1
elif operator == "-":
current_value -= numbers[next_index]
operator_list[1] -= 1
elif operator == "*":
current_value *= numbers[next_index]
operator_list[2] -= 1
else:
if current_value < 0:
current_value = -(-current_value // numbers[next_index])
else:
current_value //= numbers[next_index]
operator_list[3] -= 1
if sum(operator_list) == 0:
result.append(current_value)
return
else:
for j in range(4):
if operator_list[j] != 0:
dfs(current_value, next_index + 1, case[j], operator_list[:])
for i in range(4):
if operators[i] != 0:
dfs(numbers[0], 1, case[i], operators[:])
print(max(result))
print(min(result))
숫자의 최대 개수가 11개이기 때문에 연산자의 최대 개수는 10개이다.
연산자의 종류는 총 4개 있으므로 만약 + 3개, - 3개, * 2개 % 2개 라면
경우의 수가 10! / 3! 3! 2! 2! 정도이기 때문에
완전 탐색으로 풀어도 시간 초과가 나지 않을 것이라 생각했다.
따라서 DFS를 사용하여 탐색을 진행하였으며 최대 depth까지 갔을 때
즉, operators = [0, 0, 0, 0]이 될 때까지 값을 계산하고 결과를 result 리스트에 넣어주었다.
특이사항으로는 각 Path마다 operator 리스트를 따로 관리해야 되기 때문에 인자로 복사본인 opertators[:]를 넣어주었다.