1023번: 괄호 문자열

https://www.acmicpc.net/problem/1023

#include<cstdio>
typedef long long ll;
ll dp[51][51], k;
int n;
int main() {
    scanf("%d%lld", &n, &k);
    for (int j = 0; j <= n; j++) {
        dp[0][j] = 1;
        for (int i = 1; i <= j; i++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
    if (n & 1) {
        for (ll i = 1LL << n - 1; i; i /= 2) putchar(i&k ? ')' : '(');
    }
    else if (k >= (1LL << n) - dp[n / 2][n / 2]) puts("-1");
    else {
        int x = n / 2, y = n / 2, ck = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (ck) {
                if (k < 1LL << i) printf("(");
                else k -= 1LL << i, printf(")");
            }
            else {
                if (k < (1LL << i) - dp[x - 1][y]) {
                    printf("(");
                    x--;
                    if (!x) ck = 1;
                }
                else {
                    printf(")");
                    k -= (1LL << i) - dp[x - 1][y];
                    y--;
                    if (x > y) ck = 1;
                }
            }
        }
    }
    return 0;
}