[백준 16638번] 괄호 추가하기 2 (Python)

N = int(input())//2
eq = input()
result = -1e12
for bit in range(1<<N):
  if bit&(bit<<1):
    continue
  eq1 = [*eq]
  for i in reversed(range(N)):
    if bit&(1<<i):
      eq1.insert(i*2+3,")")
      eq1.insert(i*2,"(")
  result = max(result,eval("".join(eq1)))
print(result)

간단한 비트마스킹 문제

괄호 추가하기 [백준 16637번] 괄호 추가하기 (Python3) (tistory.com) 를 풀고나서 괄호 추가하기 2도 풀어야지 하고 묵혀놨다가 까먹고 몇 개월이 지나고 나서야 풀게 되었다.

 

파이썬의 eval 함수를 이용하면 괄호 추가하기보다 훨씬 쉽게 해결할 수 있다.

 

풀이를 설명하면,

1. 비트마스킹을 이용하여 비트가 1인 지점에 괄호를 추가한다. 이때 괄호가 겹치면 안되므로 1이 2개가 연속으로 나와선 안된다.

2. 1에서 괄호를 추가한 수식을 eval 함수로 값을 구한다.

3. 최댓값을 출력한다.

 

괄호를 추가할 때, 뒤에서부터 추가하는 것이 좋다. 왜냐하면 앞에서부터 추가하면 인덱스가 밀리기 때문에 삽입하기 까다로워지기 때문이다.