[백준] [Python] 14888번 연산자 끼워넣기 - 백트래킹

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

14888번: 연산자 끼워넣기

 

 

 

Python

n = int(input())
arr = list(map(int, input().split()))
op = list(map(int, input().split()))

maxi = -10**10
mini = 10**10
def back(k,idx,nt):
    global maxi,mini
    #print(k,op,nt)
    if k == n-1:
        maxi = max(maxi,nt)
        mini = min(mini,nt)
        #print()
        return
    #for i in range(idx,n): 
    if op[0]:
        op[0]-=1; back(k+1,idx+1,nt+arr[idx+1]); op[0]+=1
    if op[1]:
        op[1]-=1; back(k+1,idx+1,nt-arr[idx+1]); op[1]+=1
    if op[2]:
        op[2]-=1; back(k+1,idx+1,nt*arr[idx+1]); op[2]+=1
    if op[3]:
        op[3]-=1;
        if nt<0:
            back(k+1,idx+1,-(-nt//arr[idx+1]));
        else:
            back(k+1,idx+1,nt//arr[idx+1]);
        op[3]+=1

back(0,0,arr[0])
print(maxi)
print(mini)