[백준] 16638번 : 괄호 추가하기 2

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

16638번: 괄호 추가하기 2

해당문제는 식에다가 괄호를 추가하지 않거나 추가했을때의 모든 경우의수의 값을 구하여 최대값을 구하는 문제로 완전탐색, 구현 문제 입니다. 연산자의 우선순위는 곱하기가 제일 우선순위가 높고 그다음에 빼기, 더하기 임으로 곱하기는 괄호를 해도 식에 결과에는 상관이 없기때문에 곱하기 연산자는 무시합니다. 또한 빼기 더하기 연사자에 괄호를 추가할때 이전에 있던 연산자에 괄호가 추가되어있을경우 또 괄호를 추가하게되면 2개의 연산자에 괄호가 생기니 이전에 연산자가 있으면 괄호 또한 추가해서는 안된다.

 정리하자면

1. 곱하기 연산자는 괄호를 추가하지 않아도 된다. ( 계산식에 영향을 끼치지 않는다. )

2. 더하기 연산자와 빼기 연산자는 이전에 있던 연산자가 괄호가 있을경우 괄호를 추가하지 않는다.

3. 1번과 2번을 제외한 사항에는 괄호연산자가 있는경우와 없는경우 모두 체크해본다.

 

재귀함수를 이용하여 문제를 해결하였습니다 ( 괄호가 있는경우, 괄호가 없는경우 )

N = int(input())
expression = str(input())

maxvalue = -int(1e10)
def calExpression(current,depth):
    global maxvalue
    if depth == N:
        maxvalue = max(maxvalue, eval(current))
        return
    
    
    newcal1 = current + expression[depth] + expression[depth + 1] # 괄호연산 추가되지않은식
    newcal2 = current[:len(current)-1] + '('+ current[-1] + expression[depth] + expression[depth + 1] + ')' # 괄호연산을 추가 한 식
    newdepth = depth + 2
    if expression[depth] == '*': # 곱하기인 경우에는 그냥 붙힌다 괄호의 우선순위가 상관 없기 때문이다.
        calExpression(newcal1, newdepth)
    else:
        if current[-1] == ')': # 괄호가 이미 추가되어있다면 괄호연산을 하지 않는 값을 추가해야한다.
            calExpression(newcal1, newdepth) # 연산자와 숫자를 더한다.
        else:    
            calExpression(newcal1, depth + 2) # 괄호를 계산한것
            calExpression(newcal2, depth + 2) # 괄호를 계산하지 않을것
      
calExpression(expression[0], 1)      
print(maxvalue)