16637 괄호 추가하기

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

 

 

 

 

 

문제 접근

괄호를 넣지않고 미리 계산하는 방식으로 dfs를 써서 구현했다.

괄호를 쓰지않는경우, 4칸을 묶는경우, 그 이상 묶는경우 3가지로 구분했다.

괄호를 쓰지않으면 처음 인덱스에서 2칸을 건너가면 된다.

괄호를 쓰는경우 4칸을 건너가서 묶어 계산하면 되고

만약 그이상 묶는경우라면 굳이 6칸을 묶을필요없이 4칸묶고 2칸묶는것과 결과가 같다.

그래서 4칸묶기와 2칸묶기 경우로 나눠서 dfs를 만들었더니 해결됐다.

 

푸는도중 연산을 어떡할까 하다가 eval로 해결된다는걸 검색후에 알았다.

 

 

 

 

 

 

코드

import sys

input = sys.stdin.readline

N = int(input())
exp = input()
ans = float("-inf")


#4칸뒤까지 계산먼저 하고 2칸뒤 계산으로 재귀 반복
def dfs(i, val):
  global ans
  if i >= N:
    ans = max(ans, eval(val))
    return
  if i + 4 <= N:
    dfs(i + 4, str(eval(str(val) + exp[i] + str(eval(exp[i+1:i + 4])))))
  if i + 2 <= N:
    dfs(i + 2, str(eval(val + exp[i:i + 2])))

dfs(1, exp[0])
print(ans)