15658: 연산자 끼워넣기 (2)

• 이 문제는 14888: 연산자 끼워넣기와 정답 코드가 같다
• 연산자의 개수가 N-1 보다 크거나 같아도, dfs를 통해 모든 경우를 탐색하기 때문에 같은 return 조건 (if depth == N)과 재귀 방식으로 최솟값을 찾을 수 있다

import sys

def dfs(depth, result, op1, op2, op3, op4):
    global max_result
    global min_result

    if depth == N:
        max_result = max(max_result, result)
        min_result = min(min_result, result)
        return

    if op1:
        dfs(depth+1, result + A[depth], op1 - 1, op2, op3, op4)
    if op2:
        dfs(depth+1, result - A[depth], op1, op2 - 1, op3, op4)
    if op3:
        dfs(depth+1, result * A[depth], op1, op2, op3 - 1, op4)
    if op4:
        dfs(depth+1, int(result / A[depth]), op1, op2, op3, op4 -1)

N = int(input())
A = list(map(int, input().split()))
operator = list(map(int, input().split()))

max_result = int(-1e9); min_result = int(1e9)
dfs(1, A[0], operator[0], operator[1], operator[2], operator[3])
print(max_result); print(min_result)