백준 10422번 괄호

문제 링크 : https://www.acmicpc.net/problem/10422

10422번: 괄호

문제 설명

괄호 문자열의 길이가 주어졌을 때, 올바른 괄호 문자열의 개수를 구하는 문제이다.

출력에서 10억+7로 나눈 나머지를 출력하라는걸 보니 냄새가 난다. 킁카킁카..

 

풀이

다이내믹 프로그래밍 문제입니다!

풀이 설명에 앞서, 문자열 길이 L이 홀수이면 짝이 안맞는 것이니 바로 0을 출력하자!

 

길이에 따른 괄호 문자열의 예시를 들어보자면,

1. L = 2 -> ()  1가지이다.

2. L = 4 -> ()(), (()) 2가지이다.

3. L = 6 -> ()()(), (())(), ()(()), ((())),(()()) 5가지이다.

 

그렇다면 L이 5000개라면? 직접 구할 수 없다. 따라서 나눠야한다.

 

1. ()(((...4998개...))) -> L = 2 와 L = 4998 로 나눌 수 있다!

2.((...3000개...))((..2000개..)) -> L = 3000 과 L = 2000 으로 나눌 수 있다!

 

이런 식으로 중간 값 k를 기준으로 좌측과 우측으로 나누고, 이 결과가 0이 될 때까지 재귀호출을 이용해 나눠주면 된다!

재귀 호출을 할 때 기저사례(끝까지 갔을 때)는 L == 0 일 때 1을 리턴하고,

기존에 구한 d[L] 값이 존재한다면 d[L]을 리턴한다.

 

소스 코드

#include <iostream>
#include <cstring>
using namespace std;
long long d[5001]; //문자열 길이가 i 일때 개수
long long mod = 1000000007LL;
long long go(int L) {
    if (L == 0) return 1; // 빈 문자열
    else if (d[L] >= 0) return d[L]; // 0개도 처리하기 위함
    d[L] = 0;
    for (int i = 2; i <= L; i+= 2) {
        d[L] += (go(i - 2) * go(L - i));
        d[L] %= mod;
    }
    return d[L];
}
int main()
{
    memset(d, -1, sizeof(d));
    int t; scanf("%d", &t);
    while (t--) {
        int L; scanf("%d", &L);
        if (L % 2 == 1) { //홀수일 때?
            printf("0\n");
        }
        else {
            printf("%lld\n", go(L));
        }
    }
    return 0;
}

 

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~