[dfs/백준] 14888번: 연산자 끼워넣기

-문제: https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

간단한 문제인데 괜히 어렵게 생각해서 틀린 문제. 

각각의 연산자를 문자로 바꾸고, 문자에 해당하는 연산을 하고,, 

 

문제해결 키는 숫자의 순서는 바뀌지 않으므로 연산들을 무작위로 나열한 다음 

숫자,연산자,숫자,연산자 순으로 값을 계산하면 되는데 이거를 dfs가 해준다. 

dfs의 파라미터로 숫자 위치 알려주는 i와 이전까지의 계산 결과인 now를 설정한다. (이 부분이 생각하기 어려웠다)

 

무작위로 나열하는 것은 if문들로 알 수 있다. 각각의 연산을 한번씩 한다음 dfs를 돌린 후 다시 연산 값 복귀. 

연산의 갯수가 0개인지 그 초과인지 어떻게 구별할 줄 몰랐는데 operation>0을 이용하면된다. 

n= int(input())
data=list(map(int,input().split()))
add, sub, mul, div = map(int,input().split())

min_value= 1e9
max_value = -1e9

def dfs(i,now):
    global max_value, min_value, add, sub, mul, div 
    
    if i==n:
        min_value=min(min_value,now)
        max_value = max(max_value,now)
        
    else:
        if add>0:
            add-=1
            dfs(i+1, now+data[i])
            add+=1
        if sub>0:
            sub-=1
            dfs(i+1, now- data[i])
            sub+=1
        if mul >0 :
            mul-=1
            dfs(i+1, now*data[i])
            mul+=1
        if div >0:
            div-=1
            dfs(i+1, int(now/data[i]))
            div+=1
            
dfs(1,data[0])
print(max_value)
print(min_value)