백준 2747, 2748 피보나치 수

오늘 간단한 피보나치 수열 문제를 풀다가 의외의 복병에 만나서 헤매게 되었다.

백준 2747문제 n번 째 = 45 까지

백준 2748문제 n번 째 = 90 까지

문제의 형태는 같은데 입력 받을 수 있는 수의 크기가 차이나는 문제였다.

2747번 문제를 아무 생각없이 배열과 반복문을 사용해서 제출했는데 "틀렸습니다"

왜그런가 하고 재귀함수를 써서 했더니 "정답"

그리고 2748번 문제는 2747을 복붙했더니 역시나 "틀렸습니다"

다시 원래 배열과 반복문을 사용했더니 "정답"

왜그럴까?

정답은 속도 차이에 있었다.

2747번 문제는 45번까지라 단순히 재귀함수를 사용해서 풀게끔 의도가 되어있었다. (값이 작음)

하지만 2748번 문제는 n 이 90까지인데 재귀함수를 사용할 경우 호출이 누적되면서 실행시간이 매우 오래걸린다.

그래서 원래 풀었던 반복문을 사용해서 풀었어야 했다.

그런데 반복문을 사용해서 풀었는데도 처음에는 틀렸었다.

그래서 이유를 찾아봤더니, 배열을 int형으로 선언해서 틀렸다.

자료형의 크기를 간과하고있었다.

int 는 4byte  -2,147,483,648 ~ 2,147,483,647

long 은 8byte -9223372036854775808 ~ 9223372036854775807

실제로 피보나치 45번째 수와 90번째 수를 구해보았다.

45번 째 수 : 1134903170

90번 째 수 : 2880067194370816120

자료형의 크기를 벗어나서 에러가 발생했다.

여태 자료형 크기 때문에 에러난적이 없어서 생각지도 못했는데 주의해야겠다.

2747번 코드

2748번 코드