[ 백준 ] 14888번 : 연산자 끼워넣기 (파이썬)

문제 )

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

14888번: 연산자 끼워넣기

 

[ 풀이 ]

Baekjoon 사이트에는 이 문제가 Backtracking Algorithm이라고 분류되어있길래 Backtracking방법으로 풀어야 하나 했는데, promising한 node들을 추려줘야하는데 그 기준이 없는거 같았다. 

Maximum과 Minimum값을 둘 다 구해줘야하기 때문에 그냥 모든 경우의 수를 확인해야만 한다. 

 

< calculate Function의 Algorithm > -Recursive Function 사용

✔ 숫자의 갯수 → N
✔ 숫자가 있는 배열 → num
✔ '+, -, x, / ' 각 연산의 갯수 → add,sub,mul,div 
✔ 현재 값 → now
✔ 최대값 , 최솟값 → maxi, mini 
✔ 숫자배열 num에 접근하는 index → idx (1~N)

If 계산을 마치면,
           1. 새로 구한 현재값(now)와 maxi값 중 더 큰 값을 maxi값으로 update한다
           2. 새로 구한 현재값(now)와 minii값 중 더 작은 값을 mini값으로 update한다
Else
           1.  If '+'연산이 존재하면
                     Ⅰ.  calculate(idx+1,now+num[idx],add-1,sub,mul,div) 
           1.  If '-'연산이 존재하면
                     Ⅰ.  calculate(idx+1,now-num[idx],add,sub-1,mul,div)
           1.  If 'x'연산이 존재하면
                     Ⅰ.  calculate(idx+1,now*num[idx],add,sub,mul-1,div)
           1.  If '/'연산이 존재하면
                     Ⅰ.  calculate(idx+1,int(now/num[idx]),add,sub,mul,div-1)

 

 

- python code 

maxi=-1e9
mini=1e9
def calculate(idx,now,add,sub,mul,div):
    global N,maxi,mini
    if idx==N:
        maxi=max(now,maxi)
        mini=min(now,mini)
        return
    else: 
        if add :
            calculate(idx+1,now+num[idx],add-1,sub,mul,div)
        if sub:
            calculate(idx+1,now-num[idx],add,sub-1,mul,div)
        if mul:
            calculate(idx+1,now*num[idx],add,sub,mul-1,div)
        if div:
            calculate(idx+1,int(now/num[idx]),add,sub,mul,div-1)


N=int(input())
num=list(map(int,input().split()))
add,sub,mul,div=map(int,input().split()) # +, -,x,/
now=num[0]
calculate(1,now,add,sub,mul,div)
print(maxi)
print(mini)