16637번. 괄호 추가하기

http://boj.kr/16637 

16637번: 괄호 추가하기

 

 

모든 경우를 살펴야 하는 완전탐색 문제이다. 각 숫자를 처음부터 보면서, 이번 숫자가 먼저 계산되는 경우와 괄호 때문에 나중에 계산되는 경우를 각각 나눠서 재귀를 호출하면 모든 경우를 다 볼 수 있다.

1+2*3 가 있다고 하고, 이번 숫자는 1이라고 해보자. 1이 먼저 계산되는 경우는 (1+2)*3 일 것이고, 먼저 계산되지 않는 경우는 괄호가 뒤에 있어서 1+(2*3)인 경우일 것이다. 모든 숫자에 대해서 가능한 케이스는 먼저 계산되는 케이스이거나, 괄호 때문에 나중에 계산되는 케이스가 전부이므로 이렇게 두 경우를 보면 모든 케이스를 다 살펴볼 수 있다.

 

재귀함수의 매개변수는 idx, ret인데 idx는 연산자의 인덱스를 말한다. 왜 갑자기 연산자의 인덱스를 보냐?고 할 수도 있는데, 뭐 숫자의 인덱스나 연산자의 인덱스나 똑같다. ret는 지금까지 계산된 결과이다. 문제에서 식은 순서대로 계산되며, 두 번 괄호가 쳐질 수 없다고 했으므로 앞에서부터 ret을 계산하면 된다.

 

다시 돌아가서, 이번 숫자가 먼저 계산되는 경우, 그러니까 (1+2)*3일 때는 사실 순서대로 계산하면 된다. 이번 숫자가 1이고 다음 숫자가 2이므로, 1과 2를 더하면 된다. 그리고 재귀함수를 호출할 때는 이번 숫자에 대한 계산이 끝났으므로 idx를 1 증가시켜서 호출하면 된다.

 

나중에 계산되는 경우, 그러니까 1+(2*3)같은 경우는 2*3을 먼저 계산한 후, 1+(2*3의 결과)를 다시 계산해서 그 다음에 그 결과를 가지고 재귀를 호출한다. 여기서 결과라는건 계산의 결과인 ret을 의미한다. 여기서 주의해야 할 점은 이번에 본 숫자는 1인데 2칸 앞서 나가서 3까지 계산해버렸으므로, 다음 idx는 2를 더한 idx+2가 될 것이다. 

 

import sys


def divide_num_operator(string, num, operator):
    for i in string[:-1]:
        if i.isdigit():
            num.append(int(i))
        else:
            operator.append(i)


def calc(n1, n2, operator):
    if operator == '*':
        return n1 * n2
    elif operator == '+':
        return n1 + n2
    elif operator == '-':
        return n1 - n2


def dfs(idx, ret):
    global max_sum
    if idx >= len(operator):
        max_sum = max(max_sum, ret)
        return

    # 이번에 계산 되는 경우
    dfs(idx+1, calc(ret, num[idx+1], operator[idx]))

    # 이번에 계산되지 않는 경우->뒤에가 먼저 계산되는 경우(괄호가 나보다 뒤에 있음)
    if idx+1 < len(operator):
        dfs(idx+2, calc(ret, calc(num[idx+1], num[idx+2], operator[idx+1]), operator[idx]))


def solution(arr):
    divide_num_operator(arr, num, operator)

    dfs(0, num[0])


max_sum = float('-inf')
input = sys.stdin.readline
N = int(input())
arr = input()
num, operator = [], []
solution(arr)
print(max_sum)