[BOJ2748][C++] 피보나치 수 2

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

예제 입력

10

 

예제 출력

55

 

 

힌트

  

 

코드

 

#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long n = 0, a = 0, b = 1;        
    // long n = 0, a = 0, b = 1; 도 됨. 
    // unsigned는 높은 번째의 피보나치 수를 양수로 표현하기 위함.
    // unsigned를 사용하지 않을 경우 큰 피보나치 수가 음수로 표현됨. (그러나 정답 처리됨.)                                    
 
    cin >> n;
 
    // n번 동안 a와 b를 swap하여 더한 수를 b에 저장. 
    // 0 1 1 2 3 5 8 13 21 34 ...
    for (int i = 0; i < n - 1; ++i) {
        unsigned long tmp = b;
        b = a + b;
        a = tmp;
    }
 
    cout << b << endl;
 
    return 0;
}

---

- '[BOJ2747] 피보나치 수 문제'에서 제출했던 코드를 그대로 복붙해서 제출했더니 틀려버렸다.

- 문제점은 int 자료형으로는 90번째의 피보나치 수를 표현할 수 없다는 점이었다. (90번째 피보나치 수 : 2713352312)

  (int형은 4바이트(32비트)이므로 -2^31 ~ 2^31-1(–2,147,483,648 ~ 2,147,483,647) 범위 안에 드는 수만 표현할 수 있음.)

- 그래서 long 자료형을 사용하였고, 높은 번째의 피보나치 수를 양수로 표현하기 위해 unsigned 부호형을 함께 붙였다. (unsigned를 붙이지 않아도 정답 처리됨.)

- BOJ 피보나치 수 문제 관련 풀이법 소개 : https://www.acmicpc.net/blog/view/28