연산자 끼워넣기

💻 입력 조건

• 첫째 줄에 수의 개수 N(2 <= N <= 11)이 주어집니다.
• 둘째 줄에는 A1, A2, ..., An이 주어집니다.(1 <= Ai <= 100)
• 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(x)의 개수, 나눗셈(/)의 개수입니다.

💻 출력 조건

• 첫째 줄에 만들 수 있는 식의 결과의 최댓값을 출력합니다.
• 둘째 줄에는 최솟값을 출력합니다.
• 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어집니다. 또한 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고 10억보다 작거나 같습니다.

💻 입력 예시1

2
5 6
0 0 1 0

💻 출력 예시1

30
30

💻 입력 예시2

3
3 4 5
1 0 1 0

💻 출력 예시2

35
17

💻 입력 예시3

6
1 2 3 4 5 6
2 1 1 1

💻 출력 예시3

54
-24

📖 문제 해결
(1) dfs를 이용하지 않은 풀이
처음으로 작성한 풀이는 dfs를 이용하지 않고 permutations를 이용하여 연산 순서의 모든 경우의 수를 계산한 후 각 케이스마다 for 문을 이용하여 연산 순서대로 계산하는 방식을 이용하였습니다. 각 경우마다의 결과를 result라는 이름의 list에 넣은 후 result 내의 max 값과 min 값을 max 함수 및 min 함수를 이용하여 구하였습니다.

(2) dfs를 이용한 풀이
dfs를 이용하는 해결 방법이 떠오르지 않아 책의 풀이를 보고 이해한 후 다시 작성한 풀이입니다. 해당 풀이를 통하여 permutations 함수 대신 dfs를 이용하여 연산 순서의 모든 경우의 수를 고려할 수 있다는 것을 알 수 있었습니다. (1) 번 풀이와 마찬가지로 result라는 이름의 list에 각 경우마다의 결과를 넣어 max 값과 min 값을 구하였습니다.

# solution 1. dfs를 이용하지 않은 풀이

import operator
from itertools import permutations

n = int(input())
a_list = list(map(int,input().split()))
oper_num = list(map(int,input().split()))

base_ops = [operator.add, operator.sub, operator.mul, operator.floordiv]

operators = []
for i in range(4):
    for num in range(oper_num[i]):
        operators.append(base_ops[i])

oper_case = permutations(operators,len(operators))
oper_case = set(oper_case)

result_list = []

for oper_list in oper_case:
    
    result = None
    
    for i in range(n):
        
        if result == None:
            result = a_list[i]
            continue

        if oper_list[i-1] == operator.floordiv and result < 0 :
            result = - oper_list[i-1](-result,a_list[i])
            
        result = oper_list[i-1](result,a_list[i])
        
    result_list.append(result)

max(result_list)
min(result_list)

# solution 2. dfs를 이용한 풀이

n = int(input())
a_list = list(map(int,input().split()))
add, sub, mul, div = list(map(int,input().split()))

result = []

def dfs(i, now):
    
    global result, add, sub, mul, div
    
    if i == n :
        result.append(now)
    
    if add > 0:
        add -= 1
        dfs(i+1, now + a_list[i])
        add += 1
        
    if sub > 0:
        sub -= 1
        dfs(i+1,now -  a_list[i])
        sub += 1
        
    if mul > 0:
        mul -= 1
        dfs(i+1, now * a_list[i])
        mul += 1
        
    if div > 0:
        div -= 1
        dfs(i+1, int(now / a_list[i]))
        div += 1
    
    return result

result_list = dfs(1, a_list[0])

print(max(result_list))
print(min(result_list))