Problem
https://www.acmicpc.net/problem/1003
Solution
오답 코드 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
int count0 = 0;
int count1 = 0;
int fibonacci(int n) {
if (n == 0) {
count0++;
return 0;
} else if (n == 1) {
count1++;
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
int main(void)
{
int t;
scanf("%d", &t);
int n[t];
for (int i = 0; i<t; i++)
{
scanf("%d", &n[i]);
}
for (int i = 0; i<t; i++)
{
fibonacci(n[i]);
printf("%d %d\n", count0, count1);
}
}
위와 같이 코드를 짜니 입력을 “3 0 0 0”으로 했을 때 이전에 사용된 변수의 값이 계속 더해져서 결과가 나왔다. 이에 초기화가 필요하다고 판단하여 아래와 같이 for문 안에 변수초기화를 넣었다.
오답 코드 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
int count0;
int count1;
int fibonacci(int n) {
if (n == 0) {
count0++;
return 0;
} else if (n == 1) {
count1++;
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
int main(void)
{
int t;
scanf("%d", &t);
int n[t];
for (int i = 0; i<t; i++)
{
scanf("%d", &n[i]);
}
for (int i = 0; i<t; i++)
{
count0 = 0;
count1 = 0;
fibonacci(n[i]);
printf("%d %d\n", count0, count1);
}
}
하지만 위 코드는 결과값은 제대로 나오지만 시간초과로 오답처리됐다.
오답 코드 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
int count0;
int count1;
int fibo(int n)
{
if (n == 0) {
count0++;
return 0;
} else if (n == 1) {
count1++;
return 1;
} else {
return fibo(n-1) + fibo(n-2);
}
}
int main(void)
{
int t;
int sum0;
int sum1;
scanf("%d", &t);
int n[t];
for (int i = 0; i<t; i++)
{
scanf("%d", &n[i]);
}
for (int i = 0; i<t; i++)
{
if (n[i] == 0)
{
sum0 = 1;
sum1 = 0;
}
else if (n[i] == 1)
{
sum0 = 0;
sum1 = 1;
}
else if (n[i] == 2)
{
sum0 = 1;
sum1 = 1;
}
else if (n[i]>2)
{
sum0=0;
sum1=0;
count0=0;
count1=0;
fibo(n[i]-2);
sum0 += count0*2;
sum1 += count1*2;
count0=0;
count1=0;
fibo(n[i]-3);
sum0 += count0;
sum1 += count1;
}
printf("%d %d\n", sum0, sum1);
}
}
위 코드는 시간초과를 피하기 위해 규칙성을 이용하였다. f(4)를 구하기 위해 f(3)과 f(2)를 구해야 하는데 f(2)는 f(3)에서도 구하게 된다. 따라서 f(4)의 결과는 f(2)의 결과 x 2 + f(1)의 결과이며 이를 다시 정리하면 f(n)의 결과 = f(n-2) 결과 x 2 + f(n-3)의 결과로 나타낼 수 있다. 하지만 위 코드도 시간초과가 걸리게 됐다.
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
int main() {
int T;
int N;
int fibonacci[42][2]; //fibonacci[a][b]에서 a는 함수의 입력값
// b는 0또는 1이 출력되는 횟수.
//a가 0과 1일때의 배열의 요소를 초기화
fibonacci[0][0] = 1;
fibonacci[0][1] = 0;
fibonacci[1][0] = 0;
fibonacci[1][1] = 1;
//b가 0과 1일때를 나눠서 계산
for (int i = 2; i < 42; ++i)
{
fibonacci[i][0] = fibonacci[i - 1][0] + fibonacci[i - 2][0];
fibonacci[i][1] = fibonacci[i - 1][1] + fibonacci[i - 2][1];
}
scanf("%d", &T);
int n[T];
for (int i = 0; i<T; i++)
{
scanf("%d", &n[i]);
}
for (int i = 0; i < T; i++)
{
printf("%d %d\n", fibonacci[n[i]][0], fibonacci[n[i]][1]);
}
return 0;
}
Memo
한 페이지를 확인해보니 시간초과를 해결하기 위해 2차원 배열을 활용하여 N이 40 이하일 때 0과 1일때의 케이스를 모두 저장한 뒤 입력된 값에 해당하는 결과를 출력했다. C++로 작성된 해당 코드를 C로 바꿔 제출하니 이번에는 정답처리됐다.
Ref.
https://beginnerdeveloper-lit.tistory.com/42
https://kyurasi.tistory.com/entry/c-알고리즘-피보나치수-왜-시간초과가-뜰까