풀이

1. 연산자의 우선순위를 무시하고 앞에서부터 진행하는 것이 포인트인 듯 하다. 하나의 트리로 연산결과를 정의할 수 있다.
   
   예를들어, 5개의 수에 대한 연산을 진행할때는 위와 같이 경우의 수를 계산할 수 있다. -로 시작하는 상황에서 2L로 오는 +가 사실 두개가 올 수 있지만, 둘다 똑같은 +일 뿐이다. (그래서, 트리가 홀쭉해지는 것)

2. 위와 같이 모든 경우의 수를 탐색하는 브루트포스에서 필요 없는 부분은 제외하는 백트래킹 방법으로 문제를 풀어야한다.

• 종료조건

  if depth==n-1:
          MAX=max(temp,MAX)
          MIN=min(temp,MIN)
          return

  제일 먼저, 종료할 조건에 대해서 따져보자. 당연히, n-1 layer까지 도달하면 MAX,MIN인지 갱신하면서 종료해야한다.

• 재귀호출

  def backtrack(depth,temp):
    global MAX,MIN
    ...
  	if sign_list[0]!=0:
          sign_list[0]-=1 
          backtrack(depth+1,temp+a[depth+1]) 
          sign_list[0]+=1
  
      if sign_list[1] != 0 : 
          sign_list[1]-= 1
          backtrack(depth+1, temp-a[depth+1])
          sign_list[1] += 1
  
      if sign_list[2] != 0 : 
          sign_list[2] -= 1
          backtrack(depth+1, temp * a[depth+1])
          sign_list[2] += 1
  
      if sign_list[3] != 0 : 
          sign_list[3] -= 1
          backtrack(depth+1, int(temp/a[depth+1]))
          sign_list[3] += 1

  backtrack함수를 호출하여 재귀호출을 진행한다. 연산을 진행할 때마다 layer를 깊게 들어가야하기에 첫번째 인자 depth를 설정하여 1씩 더해준다.

  또한, 문제의 입력에서 [a,b,c,d] 와 같이, $+,-,\times,\div$ 의 순서대로 사용 가능한 횟수를 입력받았다. 실제 연산을 수행하며, temp값에 다음 계산 결과를 넘겨주면서 사용횟수를 차감한다.

  여기서, 나눗셈 연산을 진행할 때, // 연산으로 계산하면, -10.7이면, -11로 나오기 때문에, int를 사용해서 계산하도록 유의하자.
  

  당연히 백트래킹이기 때문에, 실제 연산을 진행하고, return을 하게되면, 방문횟수를 다시 늘려준다. 이는 한 depth 올라와서, 다른 연산자를 선택하고 다시 파고드는 위의 경우를 생각하고 작성하는 것이다.

전체코드는 아래와 같다.

# 14888 연산자 끼워넣기
n=int(input())
a=list(map(int,input().split()))
sign_list=list(map(int,input().split()))
MAX=-1e9
MIN=1e9

def backtrack(depth,temp):
    global MAX,MIN
    if depth==n-1:
        MAX=max(temp,MAX)
        MIN=min(temp,MIN)
        return
    
    if sign_list[0]!=0:
        sign_list[0]-=1 
        backtrack(depth+1,temp+a[depth+1]) 
        sign_list[0]+=1

    if sign_list[1] != 0 : 
        sign_list[1]-= 1
        backtrack(depth+1, temp-a[depth+1])
        sign_list[1] += 1
    
    if sign_list[2] != 0 : 
        sign_list[2] -= 1
        backtrack(depth+1, temp * a[depth+1])
        sign_list[2] += 1
    
    if sign_list[3] != 0 : 
        sign_list[3] -= 1
        backtrack(depth+1, int(temp/a[depth+1]))
        sign_list[3] += 1

backtrack(0,a[0])
print(MAX)
print(MIN)