1023 : 괄호 문자열

풀이

sgc109님 풀이 보고 구현했어요

  1. 괄호 문자열의 개수를 구하는 점화식을 구하고
  2. (1)에서 괄호 ㄴㄴ 문자열의 개수를 구하는 점화식을 구하고
  3. (2)를 역추적

하면 풀 수 있어요

코드

#include <cstdio>
#include <cstring>
typedef long long ll;

const ll inf = 0x3f3f3f3f3f3f3f3f;

int n;
ll k, dp[55][105][2];

ll go(int now, int sum, int isWrong) {
    if (now == n) {
        return isWrong || sum!=50;
    }
    ll &ret = dp[now][sum][isWrong];
    if (ret != inf) {
        return ret;
    }
    return ret = go(now+1, sum+1, isWrong)
               + go(now+1, sum-1, isWrong || sum <= 50);
}

void gogo(int now, int sum, int isWrong) {
    if (now == n) {
        return;
    }
    if (dp[now+1][sum+1][isWrong] >= k) {
        if (now == n-1 && k == 2) putchar(')');
        else putchar('(');
        gogo(now+1, sum+1, isWrong);
    }
    else {
        putchar(')');
        k -= dp[now+1][sum+1][isWrong];
        gogo(now+1, sum-1, isWrong || sum <= 50);
    }
}

int main() {
    scanf("%d %lld", &n, &k); k++;
    
    memset(dp, 0x3f, sizeof(dp));
    go(0, 50, 0);
    
    if (dp[0][50][0] < k) {
        return !puts("-1");
    }
    gogo(0, 50, 0);
    
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-11-14 12:52

Read more posts by this author