올바른 괄호 문자열을 만드는 알고리즘

1. 올바른 괄호 문자열

 

1) 모든 k = 1,2,3,..,n에 대하여 $S_{1}, S_{2},...,S_{2k-1}$에 대하여 적어도 k개의 문자가 '('이다.

 

2) 모든 $S_{1}, S_{2},...,S_{2n}$에 대하여 정확히 n개의 문자가 '('이다.

 

---------------------------------------------------------------------------------------------------------------------------

 

단순히 개수만 맞아도 올바른 괄호 문자열이 된다?

 

예를 들어 S1S2S3S4로 생각해보면

 

S1 = '('

 

S1S2S3에서 적어도 2개의 문자가 '('

 

S1이 '('이어야하는데, 이때 S1S2S3S4는 정확히 2개의 문자가 '('...

 

"모든 k = 1,2,3,..,n에 대하여 $S_{1}, S_{2},...,S_{2k-1}$에 대하여 적어도 k개의 문자가 '('이다."

 

이 조건이 길이가 2k-1인 문자열에서 적어도 k개의 문자가 '('이면 ')'의 개수는 최대 k-1개라는거니까, '('의 개수가 항상 ')' 보다 많다

 

"어떤 문자열의 임의의 접두사를 잡으면 반드시 (의 개수가 )의 개수 이상이다"

 

그래서 길이 1이면 (이 나와야하고

 

길이 2이면 () 이렇게 되거나 (( 이렇게 되거나 

 

근데 전체 문자열의 길이가 2라면, (은 1개여야하므로 ()임

 

길이 3이면 ((), ()(, (((도 가능하긴해 ())는 안될거고...

 

생각해보니까 맞는것 같네 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------

 

2. 알고리즘

 

$S_{1}$ = '('으로 설정

 

k = 2부터 n까지 순차적으로 인덱스 2k-2, 2k-1을 후보 집합에 추가

 

후보 집합에서 하나의 인덱스 x를 선택하여 $S_{x}$ = '('로 설정

 

남은 미정의된 n개의 위치에는 모두 ')'으로 할당

 

이 알고리즘은 실제로 올바른 괄호 수열을 만들고, 모든 올바른 괄호 수열은 이 과정으로 생성 가능하다.

 

 

1) 증명

 

어떤 수열 S가 위 절차로 구성되었다고 가정하자.

 

매 k단계마다 2k-2, 2k-1을 후보 집합에 추가한 다음, 후보 집합 중 하나를 '('으로 바꾼다.

 

따라서 모든 k = 1,2,3,...,n에 대하여 $S_{1}, S_{2}, ..., S_{2k-1}$중 적어도 k개의 위치는 '('으로 설정

 

미정의된 n개의 위치는 모두 ')'으로 할당하므로 정확히 n개의 '('와 n개의 ')'으로 구성되어 있다.

 

그러므로 수열 S는 올바른 괄호 수열이다.

 

 

반대로 올바른 괄호 수열 S에 대하여 $S_{1}$ = '('이다.

 

모든 k = 1,2,...,n에 대하여 $S_{1}, S_{2}, ..., S_{2k-1}$중 적어도 k개의 '('가 존재한다.

 

이전 단계 $S_{1}, S_{2}, ..., S_{2k-3}$까지 적어도 k-1개의 '('가 존재하는데 이때 인덱스 후보 집합은

 

{1,2,..,2k-3}이고 올바른 괄호 수열이므로, 반드시 '('으로 선택되지 않은 인덱스가 존재한다.

 

여기에 2k-2, 2k-1 인덱스를 추가하여 {1,2,3,...,2k-3,2k-2,2k-1}까지 만들고 여기에서 하나의 인덱스를 골라 '('을 추가하면,

 

길이 2k-1인 수열 $S_{1}, S_{2}, ..., S_{2k-1}$에서는 적어도 k개의 '('가 존재하게 된다.

 

총 '('의 개수는 정확히 n개이고 ')'의 개수는 정확히 n개이다.

 

따라서 모든 올바른 괄호 수열은 위 알고리즘으로 생성할 수 있다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------------

 

3. 문제

 

https://atcoder.jp/contests/abc407/tasks/abc407_e

E - Most Valuable Parentheses

 

 

수열 A[1], A[2],..., A[2N]에 대하여 길이가 2N인 어떤 올바른 괄호 수열 s를 생각하자.

 

s의 i번째 위치가 ')'일때, A[i]를 0으로 설정한다. 

 

이후 모든 A의 합을 구했을때, 어떤 올바른 괄호 수열 s에 대하여 이 합의 최대는 얼마일까?

 

-------------------------------------------------------------------------------------------------------------------------------

 

위에서 올바른 괄호 수열을 만드는 알고리즘에서 

 

매 단계 k단계에서 {2k-2, 2k-1}을 인덱스 후보 집합에 넣고 어떤 인덱스 x를 고를때, 가중치 A[x]가 가장 큰 인덱스 x를 고르면

 

점수의 합이 최대가 된다.

 

그 인덱스 x에 대응하는 A[x]가 가장 큰 x를 찾아 그것을 '('으로 만들면, 그 값은 0이 되지 않는다.

 

올바른 괄호 수열을 전부 구성하면 가장 큰 값들이 살아 남으니까 점수 합이 최대가 된다는 것

 

왜 그런지 생각해보자.

 

어떤 최적 해가 k = t에서 A[y] < A[x]인 인덱스 y를 선택했다고 가정하자.

 

즉, 더 작은 값을 어떤 단계에 선택했다고 가정해본다.

 

 

1) 이후 단계 k > t에서 x가 선택되지 않았다면,

 

원래 해에서는 t단계에 y를 골랐지만, 만약 y대신 x로 바꾸고 나머지 선택을 그대로 둔다면, A[y]에서 A[x]로 바뀌어야 하므로, 

 

반드시 전체 점수가 A[x] - A[y]만큼 증가한다.

 

따라서 원래 해 A[y] < A[x]인 y를 선택하는 것은 최적이 아니고 더 큰 A[x]를 선택하는 것이 최적이다.

 

 

2) 이후 단계 k > t에서 x가 선택되었다면,

 

원래 해에서는 단계 t에 y를 선택하고, 이후 단계 k = t' > t에서 x가 선택되었다.

 

만약 두 선택을 바꿔서 단계 t에 x를 고르고, 단계 t'에 y를 고른다고 하고 모든 선택은 그대로 두자.

 

그러면 단계 t에 A[x] - A[y]가 증가하고 단계 t'에 A[y] - A[x]만큼 감소해서, 점수의 변동이 0이 된다.

 

즉 단계 t에 A[x]를 선택하지 않고 이후에 A[x]를 선택했더라도, 단계 t에 A[x]를 선택하고 t'에 A[y]를 선택하도록 교환해도

 

점수가 바뀌지 않으므로, 단계 t에 A[x]를 선택하는 것이 최적의 그리디 규칙이라는 것이 변하지 않는다.

 

따라서 매 단계에 항상 가장 큰 A[x]를 선택하는 것이 최적이다.

 

 

 

이제 이 알고리즘은 우선순위 큐를 이용하면 쉽게 구현할 수 있다.

 

먼저 A[0]를 합 v에 더해주고, 매 단계 k = 1,2,..,n-1에 대하여 우선순위 큐에 A[2k-1], A[2k]를 넣어준 다음,

 

우선순위 큐에서 최댓값을 하나 빼서 v에 더해주면 끝

 

import heapq

T = int(input())

for _ in range(T):
    
    n = int(input())

    A = []

    for _ in range(2*n):
        
        a = int(input())
        A.append(a)
    
    v = A[0]

    queue = []

    for k in range(1,n):
        
        heapq.heappush(queue,-A[2*k-1])
        heapq.heappush(queue,-A[2*k])

        v += -heapq.heappop(queue)
    
    print(v)