[백준] 13699 점화식(JS)

 

13699번: 점화식

 

항상 숫자의 범위를 생각하자

 

문제는 주어진 점화식을 코드로 작성하는 간단한 문제였으나 3번이나 틀렸다.

 

결과값의 범위를 생각하지 않아서 틀린 거였다...

 

모든 값을 BigInt로 계산하니 드디어 정답..!

 

BigInt - JavaScript | MDN

 

 

BigInt로 변환하려면

1) 정수값 뒤에 n을 붙이거나 (예: 8n)

2) 함수 BigInt()를 호출해 변환할 수 있다. (예: BigInt(8))

 

또한, BigInt를 문자열로 변환하기 위해 toString() 메서드를 이용했다.

 

 

function solution(input) {
  let dp = Array.from({ length: input + 1 }, () => 0);
  dp[0] = 1n;
  dp[1] = 1n;
  for (let i = 2; i <= input; i++) {
    let sum = 0n;
    for (let j = 0; j < i; j++) {
      sum += BigInt(dp[j]) * BigInt(dp[i - j - 1]);
    }
    dp[i] = sum;
  }
  return dp[input].toString();
}

console.log(solution(3)); // 5
console.log(solution(25)); // 4861946401452