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


https://www.acmicpc.net/source/35117772 << 내 코드


골3라서 좀 방심했는데 생각보다 빡세다.


이전에 풀어온 골1~2 문제가 차라리 더 어려움 ㅋㅋㅋ


일단 백트래킹으로 괄호 만드는 부분이 이전에 했던 백트래킹이랑 뭔가 방식이 달라서


생각해내기 조금 빡셋고, 괄호 먼저 계산하는 구현도 필요함.


첨엔 숫자 왼쪽엔 '(', 오른쪽엔 ')' 넣다, 뺏다 2^20 경우의 수 만들고 


기저 사례에서 올바른 괄호인지 검사하고, 맞으면 스택 이용해서 계산했는데


n = 19일 때 존나 오래걸리네?


게다가 알고보니 괄호 사이에는 연산자 하나만 들어갈 수 있네?


그래서 아에 백트래킹할 때 '(' 와 ')'을 한 번에 만들어주고 없애주는 식으로 구현함. (여기 생각하는 게 한 10분 정도 걸린 듯)


그렇게 되니 자동으로 올바른 괄호인지 판별하는 로직도 필요 없어짐.


애초에 잘 만들어줘서 올바를 수밖에 없고, 괄호 안에 괄호가 있는 경우도 사라짐.


내가 볼 땐 상어 문제들보다 이게 압살임.


ㄹㅇ 티어는 상대적인건가