10422 괄호 (자바스크립트 node js)

문제

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 가지가 있다.

하지만 우리가 궁금한 것은 길이가 L인 올바른 괄호 문자열의 개수이다. 길이 L이 주어졌을 때 길이가 L인 서로 다른 올바른 괄호 문자열의 개수를 출력하는 프로그램을 만들어 보자.

 

입력

첫 번째 줄에 테스트케이스의 개수를 나타내는 T (1 ≤ T ≤ 100)가 주어진다. 두 번째 줄부터 각 테스트케이스마다 괄호 문자열의 길이를 나타내는 L이 주어진다. (1 ≤ L ≤ 5000) 

출력

각 테스트 케이스에 대해 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하시오.

==

문제 분석

일단 n이 홀수라면 절대 올바른 괄호가 될 수 없으므로 입력을 2로 나눴을 때 나머지가 1이라면 0을 answer에 추가해준다.

괄호의 길이가 2라면 만들 수 있는 것은 ()  1가지이다.

괄호의 길이가 4라면 만들 수 있는 것은 ()(), (()) 2가지이다.

이후 규칙을 찾기 위해 작성해봤을 땐

괄호의 길이가 6이라면,

1 ) 괄호의 길이가 4인 것에 () 를 추가하거나 감싸주는 것.

2 ) 괄호의 길이가 2인 것에 (()) 을 추가해주기가 있었다.

처음에는 위와 같은 규칙에 따라 현재 값 기준으로 이전 짝수들에서의 조합을 찾으면 되는 줄 알았지만 이 과정이 생각보다 어려워서 답지를 보게 되었다. 

이 문제는 여러가지 조합적 문제를 해결할 때 사용되는 카탈란 수를 활용하여 푸는 것이었다.

 

이를 코드화 하여 아래의 반복문을 만들었다.

for (let i = 2; i <= N / 2; i++) {
    for (let j = 0; j < i; j++) {
        dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % INF;
    }
}

이 코드를 통해 n의 최댓값인 5000까지 구하여 dp에 기록했는데 정답 제출시 틀림이 나왔다.

INF가 10억인 것을 감안하여 기록되는 수를 BigInt 처리 해줬더니 정답 처리 됨.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const answer = [];
const T = +input.shift();

const N = 5000;
const INF = 1_000_000_007n;

const dp = Array.from({ length: N + 1 }, () => 0n);
dp[0] = 1n;
dp[1] = 1n;

for (let i = 2; i <= N / 2; i++) {
    for (let j = 0; j < i; j++) {
        dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % INF;
    }
}

while (input.length) {
    const n = +input.shift();
    if (n % 2 === 1) answer.push(0);
    else {
        answer.push(dp[n / 2].toString());
    }
}

console.log(answer.join('\n'));