1. 문제 설명

연산자 끼워넣기 (2)

2. 문제 분석

백트래킹 문제다. 기존의 연산자 끼워넣기보다 연산자 개수가 늘어났기 때문에 백트래킹 횟수로 인해 시간 초과가 나지 않도록 주의하자.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
operators = list(map(int, sys.stdin.readline().rstrip().split()))
INF = sys.maxsize
max_num, min_num = -INF, INF

def DFS(idx, number):
    global max_num, min_num

    if idx == n - 1:
        max_num = max(max_num, number)
        min_num = min(min_num, number)
        return

    if operators[0] > 0:
        operators[0] -= 1
        DFS(idx + 1, number + numbers[idx + 1])
        operators[0] += 1
    if operators[1] > 0:
        operators[1] -= 1
        DFS(idx + 1, number - numbers[idx + 1])
        operators[1] += 1
    if operators[2] > 0:
        operators[2] -= 1
        DFS(idx + 1, number * numbers[idx + 1])
        operators[2] += 1
    if operators[3] > 0:
        operators[3] -= 1
        if number * numbers[idx + 1] < 0:
            DFS(idx + 1, -1 * (abs(number) // numbers[idx+1]))
        else:
            DFS(idx + 1, number // numbers[idx + 1])
        operators[3] += 1

DFS(0, numbers[0])
print(max_num)
print(min_num)