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

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

16637번: 괄호 추가하기

1. 수식을 입력받고 괄호를 넣을 수 있는 공간을 추가한 리스트 a를 만든다

   만약 8*3+5 가 입력되면 a는 _8_*_3_+_5_ 이런 식의 리스트다. _ 는 괄호가 들어갈 수 있는 자리

   그리고 괄호 위치를 정할 리스트 select를 a와 같은 크기로 만든다

2. 괄호를 넣을 위치를 정한다

   괄호 안에 연산자는 하나만 있어야 하기 때문에 i 번째에서 괄호가 시작하면 i+6 번째는 괄호를 닫게된다

   그 다음에는 연산자가 있기 때문에 i+8을 입력해서 다음 빈 칸부터 시작한다

   반복문의 인덱스는 여는 괄호 기준이기 때문에 4씩 증가한다

3. 괄호를 정하면 연산을 시작한다

   ans2는 괄호 안의 연산을 임시로 저장하는 변수고 cnt는 괄호를 세는 변수다

   ans1은 괄호 밖의 연산과 ans2의 결과를 합쳐서 나중에 최대값을 구한다

4. 괄호가 있으면 cnt를 증가시킨다

   cnt가 1이면 i-1에 있는 연산자를 func에 저장한다. 만약 수식의 맨 앞에 괄호가 있으면 0으로 초기화한다

   cnt가 2면 닫는 괄호이므로 func에 저장한 연산자를 불러와서 ans1과 ans2를 연산하고 cnt와 ans2를 초기화한다

5. a[i]가 숫자이면 ans1이나 ans2에 값을 저장한다

   i가 1이면 초기값이므로 괄호 여부에 맞춰서 ans1 혹은 ans2에 저장한다

   cnt가 1이고 ans2가 -1이면 괄호의 맨 처음 값이므로 ans2에 값을 저장한다

   그외의 경우에는 a[i-2]의 연산자에 맞춰서 연산한다

6. 최대값을 갱신한다. 음수가 가능하기 때문에 ans의 초기값은 음수 최대값으로 설정한다

import sys

input = sys.stdin.readline

def f(idx):
    global ans
    for i in range(idx, len(a), 4):
        if i + 6 >= len(select):
            continue
        select[i] = 1
        select[i+6] = 1
        f(i+8)
        select[i] = 0
        select[i+6] = 0

    ans1, ans2, cnt = -1, -1, 0
    for i in range(len(a)):
        if select[i]:
            cnt += 1
            if cnt == 1:
                func = a[i - 1] if i - 1 > 0 else 0
            if cnt == 2:
                if func == 0:
                    ans1 = ans2
                elif func == '+':
                    ans1 += ans2
                elif func == '-':
                    ans1 -= ans2
                else:
                    ans1 *= ans2
                cnt, ans2 = 0, -1
            continue

        if ord('0') <= ord(a[i]) <= ord('9'):
            if i == 1:
                if not cnt:
                    ans1 = int(a[i])
                else:
                    ans2 = int(a[i])
                continue

            if cnt == 1 and ans2 == -1:
                ans2 = int(a[i])
                continue

            if a[i - 2] == '+':
                if not cnt:
                    ans1 += int(a[i])
                else:
                    ans2 += int(a[i])
            elif a[i - 2] == '-':
                if not cnt:
                    ans1 -= int(a[i])
                else:
                    ans2 -= int(a[i])
            elif a[i - 2] == '*':
                if not cnt:
                    ans1 *= int(a[i])
                else:
                    ans2 *= int(a[i])

    ans = max(ans, ans1)


n = int(input())
s = list(input().strip())

a = [' ' for _ in range(n * 2 + 1)]
idx = 1
for c in s:
    a[idx] = c
    idx += 2

select = [0 for _ in range(n * 2 + 1)]
ans = -sys.maxsize
f(0)
print(ans)