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

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

 

# 백준 16637 괄호 추가하기
import sys

sys.setrecursionlimit(10**9)  # 재귀 깊이를 충분히 늘려줌 (최대 10억)
input = sys.stdin.readline

N = int(input())  # 수식의 길이 (숫자 + 연산자)
ans = float("-inf")  # 최댓값을 저장할 변수 (음수도 나올 수 있으므로 -inf로 초기화)

expression = list(map(str, input()))  # 수식을 문자열 리스트로 저장

nums = []  # 숫자들만 따로 저장할 리스트
opers = []  # 연산자들만 따로 저장할 리스트

# 인덱스가 짝수면 숫자, 홀수면 연산자
for i in range(N):
    if i % 2 == 0:
        nums.append(int(expression[i]))
    else:
        opers.append(expression[i])

len_oper = len(opers)  # 연산자의 개수


def calcul(depth, curr, prev_bracket):
    """
    depth: 현재 고려 중인 연산자의 인덱스
    curr: 괄호로 묶은 연산자의 인덱스들을 문자열로 저장
    prev_bracket: 직전 연산자를 괄호로 묶었는지 여부 (겹치는 괄호 방지용)
    """
    global ans
    global len_oper

    # 모든 연산자에 대해 괄호 선택 여부를 결정한 경우
    if depth == len_oper:
        del_ind = []  # 괄호 친 연산자의 인덱스 저장
        temp_nums = nums.copy()  # 원본 훼손 방지를 위해 복사
        temp_opers = opers.copy()

        # curr에 괄호 처리할 연산자의 인덱스가 들어있다면 실행
        if curr:
            bracket_ind = list(map(int, curr))  # 괄호 인덱스를 int로 변환
            for ind in bracket_ind:
                # 해당 연산자를 먼저 계산하여 숫자 배열에 반영
                if temp_opers[ind] == "+":
                    temp_nums[ind] = temp_nums[ind] + temp_nums[ind + 1]
                elif temp_opers[ind] == "-":
                    temp_nums[ind] = temp_nums[ind] - temp_nums[ind + 1]
                elif temp_opers[ind] == "*":
                    temp_nums[ind] = temp_nums[ind] * temp_nums[ind + 1]

                del_ind.append(ind)  # 나중에 삭제할 연산자 인덱스 기록

            # 괄호로 처리한 연산자와 숫자 제거
            while del_ind:
                del_i = del_ind.pop()
                temp_nums.pop(del_i + 1)  # 오른쪽 숫자 제거
                temp_opers.pop(del_i)  # 해당 연산자 제거

        # 괄호 처리가 끝난 후, 왼쪽부터 순차적으로 계산
        cal_ans = temp_nums[0]
        for i in range(len(temp_opers)):
            if temp_opers[i] == "+":
                cal_ans += temp_nums[i + 1]
            elif temp_opers[i] == "-":
                cal_ans -= temp_nums[i + 1]
            elif temp_opers[i] == "*":
                cal_ans *= temp_nums[i + 1]

        # 최댓값 갱신
        ans = max(ans, cal_ans)
        return

    else:
        # 직전에 괄호를 쳤다면 현재 연산자는 괄호 불가 (겹치면 안 됨)
        if prev_bracket:
            calcul(depth + 1, curr, False)
        # 괄호를 칠 수 있는 경우
        elif depth < len_oper:
            # 현재 연산자에 괄호를 치는 경우
            calcul(depth + 1, curr + str(depth), True)
            # 현재 연산자에 괄호를 안 치는 경우
            calcul(depth + 1, curr, False)


# 0번째 연산자부터 시작, curr은 빈 문자열, 아직 괄호 안 친 상태
calcul(0, "", False)

# 결과 출력
print(ans)

거창한 알고리즘이 있는줄 알았는데, 브루트포스 문제였다.