[14888] 연산자 끼워넣기

단순 backtracking

재귀를 사용했다.

 

나눗셈의 계산방식이 python과 다르므로 꼭 확인이 필요한 문제다.

또한 divide by 0 error 에 주의할 필요가 있을 것 같다.

'''
14888 연산자 끼워넣기
'''

import sys

def check_sign(number):
    if number > 0:
        return 1 
    elif number < 0:
        return -1 
    else:
        return 0

def bt(num, numbers, i, pl, mi, mu, di):

    global maxv, minv

    if pl == 0 and mi == 0 and mu == 0 and di == 0:
        maxv = max(maxv, num)
        minv = min(minv, num)
        return
    
    if pl > 0:
        bt(num+numbers[i], numbers, i+1, pl-1, mi, mu, di)
    if mi > 0:
        bt(num-numbers[i], numbers, i+1, pl, mi-1, mu, di)
    if mu > 0:
        bt(num*numbers[i], numbers, i+1, pl, mi, mu-1, di)
    if di > 0:
        if numbers[i] != 0:
            bt(abs(num)//numbers[i] * check_sign(num), numbers, i+1, pl, mi, mu, di-1)

N = int(sys.stdin.readline().strip())
numbers = list(map(int, sys.stdin.readline().split()))
plus, minus, multiply, divide = map(int, sys.stdin.readline().split())

maxv = float('-inf')
minv = float('inf')

bt(numbers[0], numbers, 1, plus, minus, multiply, divide)

print(f"{maxv}")
print(f"{minv}")