boj14888-연산자 끼워넣기 (python)

문제

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

코드 1(pypy만 통과, 1144ms) - 완전탐색

import sys
input = sys.stdin.readline
from itertools import permutations

def add(a,b):
    return a+b
def sub(a,b):
    return a-b
def mul(a,b):
    return a*b
def div(a,b):
    return int(a/b)

n = int(input())
num = list(map(int, input().split()))
n_op = list(map(int, input().split()))
all_func = [add,sub,mul,div]
operator =[]
for i, op in enumerate(n_op):
    for _ in range(op):
        operator.append(all_func[i])

per = permutations(operator, n-1)
# print(list(per))
total_min, total_max = 10e9,-10e9
result = []
for oper in per:
    total_min, total_max = 10e9,-10e9
    res = num[0]
    for i, f in enumerate(oper):
        res = f(res, num[i+1])
    result.append(res)
print(max(result))
print(min(result))

가능한 연산자 조합 순열을 구해서 모든 경우의 수 계산

코드2 (python3도 통과, 96ms) - DFS

# dfs
n = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))

minn, maxx = 10e9, -10e9
def dfs(i, total, plus, minus, multiply, devide):
    global minn, maxx
    if i == n-1:
        minn=min(minn, total)
        maxx=max(maxx, total)
        return

    if plus:
        dfs(i+1, total+num[i+1], plus-1, minus, multiply, devide)
    if minus:
        dfs(i+1, total-num[i+1], plus, minus-1, multiply, devide)
    if multiply:
        dfs(i+1, total*num[i+1], plus, minus, multiply-1, devide)
    if devide:
        dfs(i+1, int(total/num[i+1]), plus, minus, multiply, devide-1)
    
dfs(0, num[0], op[0], op[1], op[2], op[3])
print(maxx)
print(minn)

dfs로 각 경우의 수 탐색