백준 10422 : 괄호

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

10422번: 괄호

 

길이가 2인 경우,

()

​

길이가 4인 경우,

()()

(())

​

길이가 6인 경우,

()()()

(())()

()(())

((()))

(()()) 의 괄호 형태를 만들 수 있습니다.

​

이 모양은 하나의 괄호 쌍 ( ) 내에 올바른 괄호 형태를 집어넣은 형태입니다.

( 길이가 4인 괄호 형태 ) * 길이가 0인 괄호 형태 --> 괄호 6개

( 길이가 2인 괄호 형태 ) * 길이가 2인 괄호 형태 --> 괄호 6개

( 길이가 0인 괄호 형태 ) * 길이가 4인 괄호 형태 --> 괄호 6개

다음과 같이 만들어집니다.

​

따라서, dp[i]는 길이가 i일 때, 만들 수 있는 올바른 괄호 문자열의 개수입니다.

i가 홀수라면, dp[i] == 0 입니다.

i가 짝수라면, dp[i] = (dp[0] * dp[i-2]) + (dp[2] * dp[i-4]) + ... + (dp[i-2] * dp[0]) 입니다.

​

정의에 의하면 dp[0] == 0이겠지만, 0을 곱하면 0이 되므로 ( 길이가 0인 괄호 형태 )를 1로 취급하기 위해 dp[0] == 1로 초기화해주었습니다.

​

#include <cstdio>
#define MOD 1000000007
typedef long long int ll;
int t, l;
int dp[2501] = { 1, 1 };
int main() {
    scanf("%d", &t);
    for (int i = 2; i <= 2500; i++) {
        ll s = 0;
        for (int j = 1; j <= i / 2; j++) s += (ll)dp[i - j] * dp[j - 1] % MOD;
        dp[i] = (2 * s + (i % 2 ? (ll)dp[i / 2] * dp[i / 2] : 0) ) % MOD;
    }
    while (t--) {
        scanf("%d", &l);
        printf("%d\n", l % 2 ? 0 : dp[l/2]);
    }
}

 

L의 범위는 5000까지이지만, 어차피 홀수는 0이므로 dp 배열은 2500번 인덱스까지만 선언하여 짝수만 저장해주었습니다.

또, modular 연산 실행 횟수를 줄이고, 중복 계산을 방지하기 위해 i / 2까지만 합을 구한 뒤, 두 배를 취해주었습니다.

길이가 6, 10, 14, ... 인 경우의 누락되는 계산은 별도로 더해주었습니다.

처음부터 dp 배열은 long long int로 선언해도 되지만, 어차피 최종 값은 int형 범위이므로 연산할 때만 long long int로 캐스팅해주었습니다.

​

처음 코드에서 열심히 속도를 줄여본 결과 0ms에 8등으로 들어갈 수 있었습니다.