백준(B3) 2747번: 피보나치 수 (C언어 C11 C99)

코딩하는_대학생 2021. 10. 18. 22:26

코드를 보기 전에: Dynamic Programming(동적 계획법)에 대해 안다면 이 문제는 쉽게 풀수 있을것이다.

이 문제가 왜 시간초과가 나는지 모르는 사람은 밑에 있는 코드를 보고 다시 한번 도전해보길 바란다.

1
2
3
4
5
6
7
8
9
10
11

int n[46];
int fibo(int x)
{
    n[0] = 0;
    n[1] = 1;
    for (int a = 2; a <= x; a++)
    {
        n[a] = n[a - 1] + n[a - 2];
    }
    return n[x];
}

cs

코드를 설명하자면 정적배열로 호출했으므로, fibo의 모든 값은 0으로 초기화 돼 있다.
그리고 피보나치 수를 구하는 공식이 n[a] = n[a-1] + n[a-2]이므로 n의 첫번째와 두번째 값은 직접 호출해야한다.
배열을 이용해서 피보나치수를 구하면 시간이 훨씬 단축되므로, 앞으로 이러한 문제를 풀때는 배열로 풀길 바란다.
 
Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <stdio.h>
int n[46];
int fibo(int x)
{
    n[0] = 0;
    n[1] = 1;
    for (int a = 2; a <= x; a++)
    {
        n[a] = n[a - 1] + n[a - 2];
    }
    return n[x];
}
int main()
{
    int num,result;
    scanf("%d", &num);
    result = fibo(num);
    printf("%d\n", result);
    return 0;
}

cs