[백준 16637번] 괄호 추가하기(파이썬)

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

16637번: 괄호 추가하기

이 문제에서 중요한 포인트는

'어떻게 괄호를 묶는가'라는 부분.

이 부분이 상당히 난감했습니다.

'아니....모든 괄호를 묶는 경우를 다 생각해야하는데

이걸 어떻게 묶냐고....

묶을 때 각각의 데이터를 어떻게 저장하지?

이 부분이 도저히 생각이 안나서

구글링의 도움을 받았습니다.

 

제가 구글링을 통해 배운 건

"몇 번째를 묶어주는가"

하는 부분이었습니다.

solve함수를 보면

try 부분에서

현재 위치의 숫자+연산자를 뽑아냅니다.

그리고 계산을 하고

재귀로 올라갑니다.

 

 

#백준 16637번 괄호추가
import sys
sys.setrecursionlimit(10**6)


def solve(n,nu,p):
    global result
    if n==N//2 or len(nu)==1:
        result=max(result,cal(nu,p))
        return

    solve(n+1,nu[:],p[:])

    try:
        a,b=nu.pop(n),nu.pop(n)
        ca=p.pop(n)

        if ca == '+':
            nu.insert(n, a + b)
        elif ca == '-':
            nu.insert(n, a - b)
        elif ca == '*':
            nu.insert(n, a * b)

        solve(n+1,nu[:],p[:])

    except:
        0

def cal(nu,p):
    while p:
        ca=p.pop(0)
        a,b=nu.pop(0),nu.pop(0)

        if ca=='+':
            nu.insert(0,a+b)
        elif ca=='-':
            nu.insert(0,a-b)
        elif ca=='*':
            nu.insert(0,a*b)
    return nu[0]

N=int(input())
result=-2**31-1

arr=input()
num=[]
for i in range(0,N,2):
    num.append(int(arr[i]))

po=[]
for i in range(1,N,2):
    po.append(arr[i])


solve(0,num,po)

print(result)

상당히 문제가 어려워서 계속 보고 또 봐야겠네요.

솔직히 글 쓰면서도 아직 어렵다는 느낌.