[BOJ] 16637 괄호 추가하기_브루트포스

괄호 추가하기

BOJ 16637번

풀이

• DFS 또는 DP를 활용하여 전체 탐색하여 최대값을 구함

📰code

import math
answer = -math.inf

n = int(input())
s = input()

n_l = []
c_l = []

for i in range(n):        
    if i == 0: first = int(s[i])
    elif i%2 == 0: n_l.append(int(s[i]))
    else: c_l.append(s[i])
        
nn=len(n_l)

def cal(a,s,b):
    if s=='+': return a+b
    elif s=='-': return a-b
    else : return a*b
    
def dfs(d, brac = False, t_ans = first):
    global answer
    if d == nn:
        if brac == False: answer = max(answer, t_ans)
        return

    elif brac: # True
        if isinstance(t_ans,int):
            dfs(d+1, False, cal(t_ans,c_l[d],n_l[d])) # 앞에랑 괄호로 묶여서 다음엔 무조건 안하는걸로 brac =False
        else :
            dfs(d+1, False, cal(t_ans[0],t_ans[1],cal(n_l[d-1],c_l[d],n_l[d])))
    else :  # False
        dfs(d+1, False, cal(t_ans,c_l[d],n_l[d]))
        dfs(d+1, True, [t_ans,c_l[d]])
        
dfs(0)
print(answer)
        

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡