BOJ 17428 K번째 괄호 문자열

* BOJ 17428 K번째 괄호 문자열

[분류 : 다이나믹 프로그래밍]

[풀이]

  올바른 괄호 문자열이 몇 개 있을 수 있는지 생각해보자. 당연히 이 문제를 풀어본 사람은 카탈란 수를 떠올릴 수 있을거고, 아니더라도 아래 점화식을 떠올릴 수 있다.

  하지만 이런 방식은 사전순에 대한 처리를 할 수 없어진다.

  보다 간단하게 생각해보자. 현재 위치에서 어떤 괄호를 쓸 것인지를 생각해보자. 단 지금까지 구성해온 문자열에서 모두 쓸 수 있는 것은 아니다. '('과 ')' 수가 똑같을뿐만 아니라 왼쪽에서 오른쪽으로 순회할 때 ')' 수가 '(' 수보다 많지 않도록 구성해야 한다.

  따라서 정의해야 하는 함수는 현재 위치 p에서 '('가 ')'보다 r만큼 많을 때 나올 수 있는 올바른 괄호 문자열의 수를 반환하도록  한다. 또 '('을 사용했을 때의 수와 ')'을 사용했을 때의 수를 분리하여 언제 K번째가 나올 수 있는지 추적할 수 있도록 dp를 구성해주면됩니다.

rec(p, r) = 현재 위치 p에서 '('가 ')'보다 r만큼 많을 때 나올 수 있는 올바른 괄호 문자열의 수

#include<cstdio>
#include<cstring>
using ll = long long;
const int MAX_N = 50;
int N;
ll dp[MAX_N][MAX_N];
ll rec(int p, int r){
    if(p == N) return !r;
    ll& ret = dp[p][r];
    if(ret != -1) return ret;
    ret = rec(p+1,r+1);
    if(r) ret += rec(p+1,r-1);
    return ret;
}
void f(int p, int r, ll k){
    if(p == N) return;
    if(rec(p+1,r+1) <= K) {
        printf(")");
        f(p+1, r-1, K - rec(p+1,r+1));
    } else {
        printf("(");
        f(p+1, r+1, K);
    }
}
int main() {
    memset(dp, -1, sizeof dp);
    ll K;
    scanf("%d%lld",&N,&K);
    if(rec(0, 0) <= K) puts("-1");
    else f(0,0,K);
    return 0;
}