16637: 괄호 추가하기

풀이 시간

• 1h 30m
• dfs로 풀어야한다는 사실을 구글링하고 나서야 알았다 ☹️

구현 방식

• dfs max_result 갱신 및 종료 조건
  -> depth가 N-1일 때가 끝에 도달한 경우이기 때문에 최댓값을 갱신하고 종료해줘야함

• 재귀 호출 부분은 두 가지 경우로 나뉨
  1) 뒤에 괄호가 없어서 앞에서부터 이어서 계산하는 경우
  -> A+B
  -> depth+2가 N보다 작을 때까지 가능함
  2) 뒤에 괄호가 있어서 뒤부터 계산하는 경우
  -> A+(B+C)
  -> depth+4가 N보다 작을 때까지 가능함

코드

import sys

def operation(a, op, b):
    if op == '+': return a+b
    elif op == '-': return a-b
    elif op == '*': return a*b

def dfs(depth, value):
    global max_result

    if depth == N-1:
        max_result = max(max_result, value)
        return

    if depth + 2 < N: #뒤에 괄호가 없어서 앞에서부터 이어서 계산하는 경우
        dfs(depth+2, operation(value, cmd[depth+1], int(cmd[depth+2])))
    if depth + 4 < N: #뒤에 괄호가 있어서 뒤부터 계산하는 경우
        dfs(depth+4, operation(value, cmd[depth+1], operation(int(cmd[depth+2]), cmd[depth+3], int(cmd[depth+4]))))


N = int(sys.stdin.readline()[:-1])
cmd = list(sys.stdin.readline()[:-1])

max_result = -1 * int(10e9)
dfs(0, int(cmd[0]))
print(max_result)

결과