[백준] 16637번 : 괄호 추가하기

16637번: 괄호 추가하기

해당문제는 완전탐색문제입니다. 현재위치에서 계산할 경우와 그다음위치에서 계산할경우 2가지를 분기시켜 그중 최대값을 출력하면 됩니다.

예를들어 3+8*7 이 주어졌다고 가정하면, 2가지 경우가 나올 수 있습니다.

1. 3+8*7 계산식
2. 3+(8*7) 계산식

여기서 뒤에 +4가 추가된다고 가정하면

1. 이전에 있던 1번 분기점에서 3+87+4의 경우와 3+8(7+4)의 경우로 나타낼수 있습니다.
2. 이전에 있던 2번 분기점에서 3+(8*7)+4의 경우만 존재하게 됩니다. ( 중첩된 괄호는 계산 할 수 없기때문 )

N = int(input())
data = input()

def calculate(num1, num2, op):
    if op == '+':
        return num1 + num2
    elif op == '*':
        return num1 * num2
    else:
        return num1 - num2

maxresult = -int(1e9)
def dfs(idx, prev):
    if idx >= N:
        global maxresult
        maxresult = max(prev, maxresult)
        return

    if idx+3 < N:
        # 바로 다음것 부터 연산한다.
        dfs(idx+4, calculate(prev, calculate(int(data[idx+1]), int(data[idx+3]), data[idx+2]), data[idx]))

    # 자기자신부터 연산한다.
    dfs(idx + 2, calculate(prev, int(data[idx + 1]), data[idx]))

if N == 1:
    print(data[0])
else:
    dfs(1, int(data[0]))
    print(maxresult)