[백준 16637번] 괄호 추가하기 (Python3)

import sys
input = sys.stdin.readline

def cal(a,x,b):
  if x == "*":
    return int(a)*int(b)
  if x == "+":
    return int(a)+int(b)
  if x == "-":
    return int(a)-int(b)

def DFS(SUM,n):
  global result
  if n == N:
    result = max(result,SUM)
    return
  if n < N-1:
    DFS(cal(SUM,eq[n*2+1],cal(eq[n*2+2],eq[n*2+3],eq[n*2+4])),n+2)
  DFS(cal(SUM,eq[n*2+1],eq[n*2+2]),n+1)

N = int(input())
N //= 2
eq = input().strip()
result = -sys.maxsize
DFS(int(eq[0]),0)
print(result)

괄호 추가하기 2번 문제가 있길래 1은 어떤 문제인지 궁금해서 한번 풀어보았다.

1과 2의 차이는 곱하기의 우선순위인데 1번문제인 만큼 우선순위 차이가 없다 보니 쉽게 해결할 수 있었다.

 

브루트 포스를 통해 n//2개의 연산자에 대해서 i번째 연산을 할 때, i+1번 연산을 먼저 하고 i번째 연산을 하는 경우와 그냥 i번째 먼저 연산을 하는 두 가지 경우의 수로 나누어 풀 수 있다.

 

 

오늘의 교훈) 괄호 추가하기 2를 풀어보자