괄호 뒤집기

먼저 모든 문자를 )로 만든다고 생각하자. 이때 원래 (였던 위치를 뒤집는 비용의 합을 $C$라고 하자.

어떤 위치를 다시 (로 선택할 때 추가되는 비용은 원래 문자가 (라면 $-A_i$, 원래 문자가 )라면 $+A_i$이다. 올바른 괄호 문자열이 되려면 길이가 홀수인 모든 접두사 $1,3,5,\cdots,2N-1$에서 여는 괄호의 수가 각각 $1,2,3,\cdots,N$개 이상이어야 한다.

왼쪽부터 위치를 추가하면서 우선순위 큐에 해당 위치의 추가 비용을 넣는다. 홀수 위치에 도달할 때마다 지금까지 보았지만 아직 선택하지 않은 위치 중 추가 비용이 가장 작은 위치 하나를 (로 선택한다. 각 단계에서 새로 필요한 여는 괄호 하나를 가능한 최소 비용으로 선택하므로 전체 비용이 최소가 된다.

우선순위 큐를 사용하면 시간 복잡도는 $O(N\log N)$이다. Solution written by GPT5.6