반응형
코드를 보기 전에: 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 |
반응형