연산자 끼워넣기 (2)

문제

연산자 끼워넣기 1과 동일한 문제입니다. 다만 제약 조건에서 연산자의 수가 늘었습니다.

제약조건

• 2 <= N <= 11
• 1 <= A_i <= 100
• N-1 <= 연산자수의 합계 <= 4N

풀이

연산자 끼워넣기에서 사용한 코드를 그대로 사용할경우 시간초과가 났습니다. 연산자의 수가 44개일때 앞에서 작성한 코드처럼 연산자 44개에 대해 순열을 모두 구하는 순간 44!의 경우의수를 모두 구하는 것이므로, 이를 set연산자로 정리한다고 할지라도 이미 모든 경우의수를 구하는 시도부터 시간초과가 납니다. 따라서 직접 재귀로 구현해야 합니다.

코드

'''
Created by jun on 21/05/21
'''
import sys
def insert_operator(acc:int, A:list, idx:int, plus:int, minus:int, mul:int, div:int):
    #예외처리 / 답으로써 처리하면 안되는 경우
    if plus < 0 or minus < 0 or mul < 0 or div < 0:
        #최대값과 최소값에 나올수없는 값을 반환한다.
        return (-sys.maxsize, sys.maxsize)

    #남아있는 plus / minus / mul / div 값이 모두 0이상, 더 이상 고를것이 없는 경우 -> 재귀종료
    if N == idx:
        #최대값과 최소값을 정할수없다. 현재값을 최대/최소값으로 반환한다.
        return (acc, acc)

    #더 계산을 해야하는 경우 -> 재귀 진행
    plus_max, plus_min = insert_operator(acc + A[idx], A, idx + 1, plus - 1, minus, mul, div)
    minus_max, minus_min = insert_operator(acc - A[idx], A, idx + 1, plus, minus - 1, mul, div)
    mul_max, mul_min = insert_operator(acc * A[idx], A, idx + 1, plus, minus, mul - 1, div)
    div_max, div_min = insert_operator(int(acc / A[idx]), A, idx + 1, plus, minus, mul, div - 1)
    return (max(plus_max, minus_max, mul_max, div_max),
            min(plus_min, minus_min, mul_min, div_min))


N = int(input())
A = list(map(int,input().split()))
plus, minus, mul, div = map(int,input().split())
mx, mn = insert_operator(A[0], A, 1, plus, minus, mul, div)
print(mx, mn, sep='\n')

새로 알게된 사실

참고 : https://velog.io/@6047198844/%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0