[백준] 괄호 추가하기

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

16637번: 괄호 추가하기

 

DFS 알고리즘, 재귀함수를 이용하여 괄호를 추가할 수 있는 모든 경우를 나타내었다.

3+8*7-9*2 를 예로 들었을 때, rf 함수에 str(l) + o + l_ + o_ + r_ 를 출력해보면

 

0+(3+8)*7-9*2
0+(3+8)*(7-9)*2
0+(3+8)*7-(9*2)
0+3+(8*7)-9*2
0+3+(8*7)-(9*2)
0+3+8*(7-9)*2
0+3+8*7-(9*2)

(0+ 는 편의상 만들어준 식이다.)

 

이를 priority 함수를 만들어 곱셈이 우선순위인 기본적인 사칙연산과 달리 왼쪽을 우선으로 계산하여 그 중 최댓값을 answer 로 한다.

 

import sys

answer = float('-inf')

def rf(l, o, r):
    global answer

    for i in range(len(r) // 2):
        l_ = r[:2*i] + '(' + r[2*i:2*i+3] + ')'

        if len(r) >= 2*i+4:
            o_ = r[2*i+3]
            r_ = r[2*i+4:]
        else:
            o_ = ''
            r_ = ''
        
        temp = priority(str(l) + o + l_ + o_ + r_)

        if answer < temp:
            answer = temp

        rf(str(l)+o+l_, o_, r_)

def priority(s):
    operation = ['+', '*', '-']
    temp = ''
    chk = 0

    for i in s:
        if i == '(':
            chk += 1
        else:
            if i == ')':
                chk -= 1

        if chk == 0 and i in operation:
            temp = str(eval(temp)) + i
        else:
            temp += i

    return eval(temp)

def solution(N, S):
    global answer

    if N == 1:
        answer = S
    else:
        rf('0', '+', S)

    print(answer)

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()
solution(N, S)