[Baekjoon]13699번 점화식 - Javascript

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

13699번: 점화식

문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

• t(0)=1
• t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

이 정의에 따르면,

• t(1)=t(0)*t(0)=1
• t(2)=t(0)*t(1)+t(1)*t(0)=2
• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
• ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

출력

첫째 줄에 t(n)을 출력한다.

예제 입력 1 복사

3

예제 출력 1 복사

5

예제 입력 2 복사

25

예제 출력 2 복사

4861946401452

 

문제풀이(1)

t(0)=1
t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)
위의 점화식대로 문제를 풀면 되는 DP 문제이다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const N = Number(require("fs").readFileSync(filePath).toString().trim());

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

for (let i = 2; i <= N; i++) {
  let sum = BigInt(0);
  for (let j = 0; j < i; j++) {
    sum += BigInt(dp[j]) * BigInt(dp[i - j - 1]);
  }
  dp[i] = sum;
}
console.log(dp.at(-1).toString());