[백준] 16637번 괄호추가하기 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/16637

문제해결 아이디어

• 리턴 조건은 인덱스가 마지막에 도착할때 까지이다.
• 인덱스와 인덱스 까지의 계산결과를 들고 다닌다면서 dfs 순회한다.
• 계산 방법은
  • 현재 인덱스(숫자), 현재인덱스+1(기호), +현재인덱스+2 를 계산하는 경우와
  • 현재 인덱스(숫자), 현재인덱스+1(기호), (현재인덱스+2 현재인덱스+3(기호) 현재인덱스+4)
    경우이다.

소스코드

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**8)

n = int(input())

arr = input().strip()

ans = -int(1e9)

def calc(num1, op, num2):
    if op == '+': return num1+num2
    if op == '*': return num1*num2
    if op == '-': return num1-num2

def dfs(index,value):
    global ans
    if index == n-1:
        ans = max(ans, value)
        return

    if index + 2 < n:
        dfs(index+2, calc(value, arr[index+1], arr[index+2]))

    if index + 4 < n:
        dfs(index+4, calc(value, arr[index+1], calc(arr[index+2], arr[index+3], arr[index+4])))

print(ans)