티스토리 뷰

알고리즘 관련/BOJ

BOJ)10422 괄호

JASON 자손9319 2017. 3. 30. 14:27

문제: icpc.me/10422


괄호 문자열이 되려면 괄호 문자열이 채워져 나가는 과정에서 )의 개수가 (개수보다 많으면 안된다.


이를 만족하면서 채워져 나가는 길이가 N인 괄호문자열의 개수를 다이나믹 프로그래밍을 이용하여 구해주면 된다.


N이 홀수인 경우 0을 출력하고 N이 짝수인 경우 dp[n/2][n/2]를 출력하면 된다.


dp[x][y]의 정의는 (가 x개 )가 y개 까지 그려진 괄호문자열의 개수 이다.


점화식은 dp[x][y]=dp[x-1][y]+dp[x][y-1]이 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
typedef long long ll;
using namespace std;
ll dp[5001][5001];
ll t, n;
ll func(int x, int y) {
    if (x < y)return 0;
    if (x < || y < 0)return 0;
    if (x == && y == 0)return 1;
    ll &ret = dp[x][y];
    if (ret != -1)return ret;
    ret = 0;
    ret += func(x - 1, y) + func(x, y - 1);
    ret %= MOD;
    return ret;
}
int main() {
    scanf("%lld"&t);
    memset(dp, -1sizeof(dp));
    while (t--) {
        scanf("%lld"&n);
        if (n % 2)puts("0");
        else
            printf("%lld\n", func(n / 2, n / 2));
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13460 구슬탈출2  (6) 2017.03.30
BOJ)1520 내리막 길  (0) 2017.03.30
BOJ)10422 괄호  (0) 2017.03.30
BOJ)1194 달이 차오른다, 가자.  (0) 2017.03.30
BOJ)2146 다리만들기  (0) 2017.03.30
BOJ)5427 불  (0) 2017.03.30
댓글
댓글쓰기 폼