[골드 5] 10422번 괄호⭐️

문제 설명

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

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

입력

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

출력

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

풀이

숫자 범위때문에 BigInt 사용해야 함.

1 x 0개
2 () 1개
3 x 0개
4 ()(), (()) 2개
5 x 0개
6 ()()(), ((())), (())(), ()(()) 4개
7 0개
8 8개
9 0개
10 16개

규칙을 찾아봤을 때 홀수는 불가능하고, 짝수는 2^n씩 증가하는 것 같아서 아래처럼 풀었는데 틀렸다. -> 규칙을 잘못 찾은듯

1 2 3 4 5 6 7 8 9 10
0 1 0 2 0 4 0 8 0 16

const input = require("fs").readFileSync("ex.txt").toString().split("\n");
const [T, ...L] = input.map(Number);
const C = 1000000007n;

function solution(n) {
  const bigN = BigInt(n);
  let answer = 0n;
  if (bigN % 2n === 0n) {
    answer = 2n ** (bigN / 2n - 1n) % C;
  }
  console.log(answer.toString());
}

L.map((el) => solution(el));

카탈란 수 활용

const [_, ...input] = require("fs")
  .readFileSync("ex.txt")
  .toString()
  .trim()
  .split("\n")
  .map(Number);
const LIMIT = 1000000007n;
let dp = Array(5001).fill(0n);
dp[0] = 1n;
dp[1] = 0n;

for (let i = 2; i <= 5000; i += 2) {
  for (let j = 0; j < i; j += 2) {
    dp[i] = (dp[i] + ((dp[j] * dp[i - j - 2]) % LIMIT)) % LIMIT;
  }
}

dp = dp.map((v) => (v ? v : 0n));

let answer = "";
for (let i of input) answer += `${dp[i]}\n`;

console.log(answer);

참고 블로그
https://kth990303.tistory.com/265
카탈란 수
https://cvillain.tistory.com/22