[python] 백준 16637 괄호 추가하기

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

16637번: 괄호 추가하기

 

문제 해결

• 괄호는 소괄호만 사용 가능
• 사칙연산의 순서는 무시 (곱셈 우선 하는 것 무시)
• 왼쪽 부터 계산하면서 한 번 계산할 때 마다 뒤에 괄호로 계산 한 것과 안한 것 두가지 경우가 있음
• dfs로 뒤에 괄호가 있어서 계산 한 경우와 괄호 없어서 이어서 계산하는 경우 두 가지로 계속 나눠가며 계산
• 최댓값을 구하기

 

CODE

def operator(num1, oper, num2):
    if oper == '+':
        return num1+num2
    elif oper == '-':
        return num1-num2
    elif oper == '*':
        return num1*num2
    
def dfs(idx, target):
    global ans
    if idx == n-1:
        ans = max(ans, target)
        return
    if idx +2 <n:
        dfs(idx+2, operator(target,equal[idx+1], equal[idx+2]))
    if idx+4<n:
        dfs(idx+4, operator(target,equal[idx+1],(operator(equal[idx+2],equal[idx+3], equal[idx+4]))))
if __name__=='__main__':    
    n = int(input())
    equal = list(input().rstrip())
    ans = -pow(2,31)
    for i in range(0,len(equal),2):
        equal[i] = int(equal[i])
    target = equal[0]
    dfs(0,target)
    print(ans)