BOJ 1023번 괄호 문자열

\(1\leq{N}\leq{50}\)

\(0\leq{K}\lt{2^N-1}\)

괄호 문자열(correct parenthese sequence)의 정의는 이미 잘 알려져 있다.

그리고 어떤 문자열 S가 '(' 와 ')' 로만 이루어져있는데 괄호 문자열이 아니라면 이것을 괄호ㄴㄴ문자열이라고 정의한다.

N과 K가 주어진다. 길이가 N인 괄호ㄴㄴ문자열들을 사전순으로 정렬했을 때 K번째인 문자열을 찾는 문제이다.

인덱스는 0부터 시작한다는 것에 주의하자.

우선 괄호 문자열의 개수를 구하는 방법을 알아보자.

dp[i][j] : 이미 i개의 문자가 정해졌고 짝이 지어지지않은 열린 괄호의 수가 현재 j 개일 때 괄호 문자열의 수

dp[i][j] = dp[i-1][j] + dp[i-1][j+1]

왜냐하면 각각의 위치에서는 괄호를 열거나, 닫거나 둘중 하나인데 연다면 짝이 지어지지않은

열린괄호의 수 j가 1 증가하고 닫는다면 1 감소하기 때문이다. 물론 주의해야 할 것이

짝이 지어지지않은 열린괄호의 수가 음수가 된다면, 즉 짝이 지어지지않는 열린괄호가 생긴다면

그 순간 그것은 괄호 문자열이 아니므로 dp[i-1][j-1] 은 j가 0보다 클 때만 계산한다. 이외의 경우는 0으로한다.

이것을 재귀로 구현해 본다면 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll dp[53][53];
int N;
ll go(int pos, int open){
    if(pos == N) return open==0;
    ll& cache = dp[pos][open];
    if(cache != -1) return cache;
    cache = 0;
    cache += go(pos+1, open+1);
    if(open>0) cache += go(pos+1,open-1);
    return cache;
}
 
int main() {
    memset(dp,-1,sizeof(dp));
    scanf("%d",&N);
    printf("%lld",go(0,0));
    return 0;
}
 

이런식으로 될 것이다. 그럼 반대로 괄호ㄴㄴ문자열은 어떻게 구할까?

괄호 문자열을 구하는 재귀함수의 코드에서 세가지를 변경,추가 해주어야 한다.

첫번째로 if(open>0) 조건문이다. 괄호 문자열을 구할 땐 열린괄호가 닫힌괄호보다 많아지는 순간

무조건 괄호 문자열이 아니게 되므로 저 조건문을 붙여 준 것이다. 하지만 괄호 ㄴㄴ 문자열에서는 그런 경우도

모두 세어 주어야 하기 때문에 조건문을 지워준다. 

두번째로 추가해줘야할 부분이 바로 open 인자가 음수가 될 수 있으므로

메모이 제이션을 할 때 open+N 을 해주는 것과 dp 배열의 open 부분을 2배로 늘려주는 것이다.

세번째로 추가해줘야할 부분은 기저 부분이다. 기저부분은 N개의 문자를 모두 결정했을 때 최종적으로

괄호 문자열인지 아닌지를 판단해서 0또는 1을 리턴하는 부분이다.

괄호문자열에서는 열린괄호들이 모두 제 짝을 찾아야 결과적으로 괄호문자열이 될 수 있었기 때문에

열린괄호와 닫힌괄호의 수가 같았는지를 검사해 주기 위해 open == 0 조건을 붙였다.

(수가 같았는지만 비교해도 되는 이유는 if(open>0) 조건문을 통해 중간 중간 괄호문자열이 아니게 되는 

경우를 제거해 주었기 때문이다.)

그러면 반대로 괄호 ㄴㄴ 문자열이 되려면 어떻게 되어야 할까?

그냥 단순히 open != 0 을 해주면 안되는 이유가,

)()( 와 같은 경우는 최종적으로 open 은 0이지만 중간에 열린괄호가 닫힌 괄호보다 많아지는 순간이

있기 때문에 괄호 문자열이 아니다. 이것도 세어 주기위해 부분문제의 정의를 다시 정해야한다.

dp[pos][open][wrong] : 이미 pos개의 문자가 정해졌고 짝이 지어지지않은 열린 괄호의 수가 현재 open 개이며,

중간에 괄호문자열이 아니게 되었는지의 여부 가 wrong일 때 괄호 문자열의 수

그럼 기저는 wrong 이 1이거나 open 이 0이 아닐 때 1을 반환하도록 바꿔야 할 것이다.

그리고 중간에 cnt가 음수가 될때 wrong 을 1로 서브호출 해주면된다.

그랬을 때 코드는 이렇게 바뀐다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll dp[53][103][2];
int N;
ll go(int pos, int cnt, int wrong){
    if(pos==N) return wrong || cnt!=0;
    ll&cache = dp[pos][cnt+N][wrong];
    if(cache != -1) return cache;
    cache = 0;
    cache += go(pos+1, cnt+1, wrong);
    cache += go(pos+1, cnt-1, wrong || cnt <= 0);
 
    return cache;
}
int main() {
    memset(dp,-1,sizeof(dp));
    scanf("%d",&N);
    printf("%lld",go(0,0,0));
    return 0;
}
 

그럼 이제 이걸 바탕으로 K번째 괄호 ㄴㄴ 문자열을 어떻게 찾을까?

일반적인 dp의 k번째 답찾기 문제에서처럼 하면되는데 몇가지 신경써주어야 할 부분을 말하자면

우선 마지막 문자를 결정해야 할때 k가 1또는 2일 텐데 이 이유는 '(' 또는 ')' 이기 때문이다.

'('와 ')' 중에 첫번째것이 '(', 두번째 것이 ')' 이기 때문에 1또는 2인데, 1이면 '('을 출력

2이면 ')'을 출력하면 된다. 

최종적인 코드는 이렇다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll dp[53][103][2];
int N;
ll K;
ll go(int pos, int cnt, int wrong){
    if(pos==N) return wrong || cnt!=0;
    ll&cache = dp[pos][cnt+N][wrong];
    if(cache != infl) return cache;
    cache = 0;
    cache += go(pos+1, cnt+1, wrong);
    cache += go(pos+1, cnt-1, wrong || cnt <= 0);
 
    return cache;
}
void go2(int pos, int cnt, int wrong, ll k){
    if(pos == N) return;
    if(dp[pos+1][cnt+1+N][wrong] >= k) {
        if(pos==N-1&&k==2) printf(")");
        else printf("(");
        go2(pos+1, cnt+1, wrong, k);
    }
    else {
        printf(")");
        go2(pos+1, cnt-1, wrong || cnt <= 0, k - dp[pos+1][cnt+1+N][wrong]);
    }
}
int main() {
    memset(dp,0x3c,sizeof(dp));
    scanf("%d%lld",&N,&K);
    go(0,0,0);
    if(K+1 > dp[0][N][0]) return !printf("-1");
    go2(0,0,0,K+1);
    return 0;
}