BOJ 1023 괄호 문자열

* BOJ 1023 괄호 문자열

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

  BOJ 17428 K번째 괄호 문자열을 먼저 푸는 것을 추천합니다. 사실상 거의 같은 문제입니다.

[풀이]

  올바른 괄호 문자열의 정의는 '('의 수와 ')'의 수가 같아야하며 왼쪽에서 오른쪽으로 순회할 때 ')'의 수가 '('의 수보다 많아지면 안된다. 반대로 괄호 ㄴㄴ 문자열이 되려면 위 정의 반대로 구성하면 된다. 즉,

  1. '('의 수와 ')'의 수가 다르거나

  2. 왼쪽에서 오른쪽으로 순회할 때 ')'의 수가 '('보다 많은 경우에 올바르지 않다고 판단해주면 된다.

  위를 토대로 함수 프로토타입을 정의하면 아래와 같다.

rec(v, p, r)

v : validation ')'의 수가 '('의 수를 역전했던 적이 있는지 확인하는 플래그 변수

p : 구성해야하는 문자열의 현재 위치

r : '('의 수 - ')'의 수

  r이 음수가 될 수 있다는 점만 주의해주면 어렵지 않게 구현할 수 있다.

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