BOJ 1023 괄호 문자열

사용한 알고리즘

DP, 탐색

알고리즘 설명

일단 문자의 길이가 N인 경우 잘못된 괄호 문자열의 개수를 DP로 찾을 수 있다.
문제를 분석하자.
길이가 i번째에 열린 괄호가 k개 있다면 닫힌 괄호는 n-k 개 이다.
i번째에서 열린 괄호 < 닫힌 괄호라면 이후에 모든 경우에 있어 불가능이다.
DP state를 아래와 같이 정할 수 있다.
DP(i번째 문자열, 열린 괄호 - 닫힌괄호 수, 1~(i-1)번째 문자열이 이미 잘못된 괄호 문자열인 경우)
i번째에서 열린 괄호를 쓰는 경우, 닫힌 괄호를 쓰는 경우 2가지로 DFS 탐색을 진행한다.
길이가 N이 되었을때, wrong인지 또는 열린 괄호와 닫힌 괄호 개수가 같은지 판단한다.
K번째 문자열을 찾기 위해서 탐색을 진행한다.
앞에서 채워놓은 DP 테이블을 이용하여 열린 괄호를 선택한 경우, 닫힌 괄호를 선택한 경우로 나누어서 K보다 큰지 작은지로 두 괄호중 한가지를 선택한다.
닫흰 괄호를 선택할 경우 열린 괄호를 선택한 경우의 수를 K에서 빼준다.
이러한 형태로 탐색하며, 한가지 예외 처리는 마지막 괄호를 선택하면서 열린괄호 선택이 가능한데 K가 2인 경우는 이미 wrong 괄호로 둘다 열린괄호와 닫힌괄호 둘다 선택 가능한 경우로, 알파벳 법칙의 따라 닫힌 괄호를 출력해 주어야한다.
DP 구성시 열린 괄호 - 닫흰 괄호 수는 음수 값이 나올 수 있어 이를 막기 위해서 Bias 값인 N를 더하여 0 <= 열린 괄호 - 닫흰 괄호 수 <= N 에 존재하도록 한다.

풀이

// baekjoon 1023 yechan
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX_N = 51;
const long long infl = 0x3c3c3c3c3c3c3c3c;

int N;
ll K;
ll dp[MAX_N][MAX_N*2][2]; // [StringPosition][OpenParenthesis][wrong_flag]

ll findDP(int pos, int open, int wrong) {
    if (pos == N) return wrong || open !=0;
    ll &ret = dp[pos][open+N][wrong];
    if (ret != infl) return ret;
    ret = 0;
    ret += findDP(pos+1, open+1, wrong);
    ret += findDP(pos+1, open-1, wrong || open <= 0);
    return ret;
}

void trackingParen(int pos, int open, int wrong, ll k) {
    if (pos == N) return;
    if (dp[pos+1][open+1+N][wrong] >= k) {
        if (pos == N-1 && k==2) printf(")");
        else printf("(");
        trackingParen(pos+1, open+1, wrong, k);
    }
    else {
        printf(")");
        trackingParen(pos+1, open-1, wrong || open <= 0, k - dp[pos+1][open+1+N][wrong]);
    }
}

int main() {
    memset(dp, 0x3c, sizeof(dp));
    scanf("%d%lld", &N, &K);
    findDP(0, 0, 0);
    if (K+1 > dp[0][N][0]) return !printf("-1");
    trackingParen(0, 0, 0, K+1);
    return 0;
}