백준 2747번 피보나치 수 [C언어]

Sol)

#include <stdio.h>

int main()
{
    int fibo[46] = {0, 1};
    int n = 0;

    for(int i = 2; i < sizeof(fibo) / sizeof(int); i++){
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }

    scanf("%d", &n);

    printf("%d\n", fibo[n]);

    return 0;
}

 

이 문제는 "의지충만#3 : 배열또는 포인터" 라는 백준 문제집에 있었다. 전에 재귀함수로 푸는 피보나치 수 문제를 푼 적이 있었기에 피보나치 수 문제는 무조건 재귀로 푸는 것이라는 잘못된 인식이 박혀있었다. 그래서 그리 어려운 문제는 아니었음에도 불구하고 처음 봤을 때 조금 당황했다. '피보나치 수 문제를 배열이나 포인터를 이용해서 어떻게 풀지..?'

하지만 피보나치 수의 점화식을 보고 풀이가 떠올랐고, 생각을 잘 해보니 재귀를 이용해 푸는 것보다는 위와 같이 배열을 이용해 푸는 편이 효율성 면에서는 훨씬 좋겠다는 생각이 들었다. 

이 문제에서는 n이 45 이하로 작게 주어졌으므로 scanf로 n을 받기 전에 배열 크기를 설정해주고, 피보나치 수도 미리 다 구해 놓았다. 하지만 만일 n이 더 커지고 배열 or 포인터를 이용해 풀어야 한다면 n을 입력받고 포인터에 malloc함수를 이용해 n만큼 메모리를 동적할당 후, 0 과 1 을 넣고 위와 같이 반복문을 똑같이 돌리면 되겠다는 생각이 들었다. 역시 생각은 여러방향으로 많이 해봐야겠다는 생각이 들었다.