개발 블로그

문제 링크 : https://www.acmicpc.net/problem/2748

문제

피보나치 수는 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번째 피보나치 수를 출력한다.

접근 방법

처음에는 재귀 함수로 풀었는데 시간 초과가 났다.

그래서 DP로 풀었는데 dp[]의 자료형을 int 형으로 지정해서 오답으로 처리됐다. F(90) = 2,880,067,194,370,816,120 이므로 dp[]는  long long 형으로 선언해줘야한다. 

F(45) = 1836311903
F(46) = 2971215073
이므로 n = 46부터 int형 범위를 넘어간다. 

* long long(8byte) : –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 
* long (4byte) : –2,147,483,648 ~ 2,147,483,647

의문) long형으로 선언해도 백준은 정답으로 처리돼서 테스트케이스에 n=90이 없나 싶었는데,

         VsCode에서도 F(90)이 정상적으로 출력된다. 이론상으로는 long long 이 맞는데 정답 처리 되는 이유를 잘 모르겠다.

#include <iostream>
using namespace std;

long long dp[91]={0,};

int main()
{
    int n; cin >> n;
    
    dp[0] = 0; dp[1] = 1;
    for(int i = 2; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n];
    return 0;
}