BOJ14888 연산자 끼워넣기

2590ms로 겨우 푼 코드

from itertools import permutations

N = int(input())
elem = list(map(int, input().split()))
tmp_a = list(map(int, input().split()))

tmp_b = []
for i in range(len(tmp_a)):
	for j in range(tmp_a[i]):
		op = ''
		if i == 0:
			op = '+'
		elif i == 1:
			op = '-'
		elif i == 2:
			op = '*'
		elif i == 3:
			op = '/'
		tmp_b.append(op)

oper_permu = list(permutations(tmp_b, len(tmp_b)))

def calc(a, op, b):
	if op == '+':
		return a + b
	elif op == '-':
		return a - b
	elif op == '*':
		return a * b
	elif op == '/':
		return int(a / b)

maxx = -9999999999
minn = 9999999999
for i in range(len(oper_permu)):
	
	tmp_result = elem[0]
	for j in range(len(oper_permu[i])):
		tmp_result = calc(tmp_result, oper_permu[i][j], elem[j+1])
	maxx = max(maxx, tmp_result)
	minn = min(minn, tmp_result)
print(maxx)
print(minn)

시간복잡도 O(2^N)

import sys
input = sys.stdin.readline

minn = 1e9
maxx = -1e9
def recur(depth, prev_result, plus, minus, mul, div):
	global minn
	global maxx
	if depth == N:
		minn = min(minn, prev_result)
		maxx = max(maxx, prev_result)
		return

	if plus:
		recur(depth+1, prev_result+elem[depth], plus-1, minus, mul, div)
	if minus:
		recur(depth+1, prev_result-elem[depth], plus, minus-1, mul, div)
	if mul:
		recur(depth+1, prev_result*elem[depth], plus, minus, mul-1, div)	
	if div:
		recur(depth+1, int(prev_result/elem[depth]), plus, minus, mul, div-1)
			

N = int(input().strip())
elem = list(map(int, input().strip().split()))
opers = list(map(int, input().strip().split()))

recur(1, elem[0], opers[0], opers[1], opers[2], opers[3])
print(maxx)
print(minn)