백준: 16637 괄호 추가하기

문제

16637번: 괄호 추가하기

 

문제 풀이

 수식이 주어질 때, 괄호를 추가하여 최대가 되는 수를 반환하는 문제이다. 괄호를 추가하기 위해서는 2가지 방법이 있을 수 있다. 예를 들어 예제 입력 1의 경우 `3 + 8 * 7 - 9  * 2`를 괄호를 추가할 수 있는 경우를 `DFS`로 탐색하는 방법은 다음과 같다.

 

• 두수 사이에 하나의 연산자 기호가 있어야 한다.
• `(3 + 8) * 7 - 9 * 2`와 같이 가장 앞의 연산자부터 우선 처리한다.
• `3 + (8 * 7) - 9 * 2`와 같이 다음의 연산자를 우선 처리한다.

 

코드

from math import inf
from sys import stdin


def dfs(idx, sub_total):
    global answer

    if idx == len(op):
        answer = max(answer, int(sub_total))
        return

    # (3 + 8) * 7 - 9 * 2 부터 시작.
    first = str(eval(sub_total + op[idx] + nums[idx + 1]))
    dfs(idx + 1, first)

    if idx + 1 < len(op):
        # 3 + (8 * 7) - 9 * 2 부터 시작
        second = str(eval(nums[idx + 1] + op[idx + 1] + nums[idx + 2]))
        second = str(eval(sub_total + op[idx] + second))
        # op를 2개 소모했으므로 idx + 2
        dfs(idx + 2, second)


if __name__ == '__main__':
    n = int(stdin.readline())
    expression = stdin.readline().rstrip()
    nums, op = [], []
    answer = -inf

    for e in expression:
        nums.append(e) if e.isdigit() else op.append(e)

    dfs(0, nums[0])
    print(answer)

 숫자와 연산자 처리를 편하게 하기 위해, 숫자와 연산자를 구분하였다. 또한 `3+4`와 같은 문자열을 `eval`로 처리해 코드가 간결하고 보기 좋아졌다.🙂