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

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

 

# 백준 16638 괄호 추가하기2
import sys

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

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

expression = list(
    map(str, input())
)  # 수식을 문자열 리스트로 저장 (예: "1+2*3" -> ['1','+','2','*','3'])

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: 괄호로 묶은 연산자의 인덱스들을 문자열로 저장 (예: "02" → 0번째, 2번째 연산자에 괄호 있음)
    prev_bracket: 직전 연산자에 괄호를 쳤는지 여부 (겹치는 괄호 방지)
    """
    global ans
    global len_oper

    # 연산자들을 전부 검사한 경우 (괄호를 어디에 칠지 결정이 끝남)
    if depth == len_oper:
        del_ind = []  # 괄호 처리한 연산자의 인덱스를 기록
        temp_nums = nums.copy()  # 원본 배열 훼손 방지
        temp_opers = opers.copy()

        # 괄호로 묶은 연산자가 있으면 먼저 처리
        if curr:
            bracket_ind = list(map(int, curr))  # 문자열 curr → int 리스트 변환
            for ind in bracket_ind:
                # 해당 연산자를 먼저 계산하여 temp_nums에 반영
                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)  # 해당 연산자 제거

        # 곱셈 먼저 처리 (*는 우선순위가 높음)
        temp_oper_len = len(temp_opers)
        i = 0
        while i < temp_oper_len:
            if temp_opers[i] == "*":
                temp_nums[i] = temp_nums[i] * temp_nums[i + 1]
                temp_nums.pop(i + 1)  # 오른쪽 숫자 제거
                temp_opers.pop(i)  # 연산자 제거
                temp_oper_len -= 1
            else:
                i += 1

        # 남은 연산자들은 왼쪽부터 순서대로 계산 (+, - 만 남음)
        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)
        else:
            # 현재 연산자에 괄호를 치는 경우
            calcul(depth + 1, curr + str(depth), True)
            # 현재 연산자에 괄호를 안 치는 경우
            calcul(depth + 1, curr, False)


# 탐색 시작 (0번째 연산자부터, 괄호 없음 상태)
calcul(0, "", False)

# 최댓값 출력
print(ans)

 

괄호 추가하기 1 문제를 풀고나서 조건 하나만 더 추가해주면 되었다.