2747번: 피보나치 수

https://www.acmicpc.net/problem/2747

2747번: 피보나치 수

n번째 피보나치 f(n)은 f(n - 1)  + f(n - 2)로 표현되는데, f(n - 1) = f(n - 2) + f(n - 3)이므로 마지막 두 피보나치 수를 저장한 뒤 피보나치 수를 출력하면 메모리와 시간을 적게 들이면서 피보나치 수를 계산할 수 있다.

#include <cstdio>

int main() {
    // 피보나치 수를 계산할 때 필요한 공간은 총 세 개이다
    // 두 개는 더할 수를 저장한 공간, 나머지 하나는 더한 수를 저장할 공간

    // fib[i % 3]: i번째 피보나치 수, n: 구할 피보나치 수의 순서
    int fib[3] = { 0, 1, }, n;
    // 구할 피보나치 수의 순서를 입력받은 뒤
    scanf("%d", &n);
    // n번째까지의 피보나치 수를 연산
    for (int i = 2; i <= n; i++)
        fib[i % 3] = fib[(i - 1) % 3] + fib[(i - 2) % 3];
    // n번째 피보나치 수를 출력한다
    printf("%d\n", fib[n % 3]);

    return 0;
}