Question

테스트 케이스 7 ~ 14 실패하는 이유

이유를 모르겠습니다

혹시 반례가 있다면 알려주시면 감사하겠습니다 :)

작성중인 코드―solution.js

1
2
3
4
5
6
7
8
9
10
11
12
function solution(n) {
  if (n === 2) return 1;

  const fibNumbers = new Array(n + 1).fill(0);
  fibNumbers[1] = 1;

  for (let i = 2; i <= n; i++) {
    fibNumbers[i] = fibNumbers[i - 1] + fibNumbers[i - 2];
  }

  return fibNumbers[n] % 1234567;
}

자료형 overflow 처리를 해주셔야할 것 같아요!

서찬영―2022.01.05 03:19

Answer 1

🚨이런 문제가 있어요
n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우가 납니다.

예를 들어

47번째 피보나치 수는 2,971,215,073이고, 이 수는 32비트 정수(ex. int) 범위를 넘어 오버플로우가 발생합니다.
100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생합니다.

💡그럼 코드를 어떻게 바꾸면 좋나요?
모든 단계에서 % 연산을 사용하여, 모든 연산에서 오버플로우가 일어나지 않게 만들어 주세요.

감사합니다. 덕분에 풀었습니다!!

2가염색체나열―2022.12.02 00:39
감사합니다!

유지민―2023.03.28 17:23
감사합니다 도움 많이 되었네요 ㅎㅎ

JAECHANGG―2023.06.21 16:38
감사합니다!!!

osw7875―2023.07.13 14:31
감사합니다ㅎㅎ 도움이 되었어요

양은진―2023.09.05 15:27
감사합니다

멜로님―2023.12.14 13:11

Ayaan

2021.12.22 22:02

테스트 케이스 7 ~ 14 실패하는 이유

작성중인 코드―solution.js

서찬영―2022.01.05 03:19

1 개의 답변

산들이

2022.11.8 16:17

2가염색체나열―2022.12.02 00:39

유지민―2023.03.28 17:23

JAECHANGG―2023.06.21 16:38

osw7875―2023.07.13 14:31

양은진―2023.09.05 15:27

멜로님―2023.12.14 13:11

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.