백준 1003번은 재귀함수의 대표적인 사용법 중 하나인 피보나치에 대해 물어보는 문제이다. 하지만 대부분의 문제가 수열의 몇 번째 수를 구하여라 같은 것을 물어보는 것과는 다르게, 이 문제는 0과 1이 각각 몇 번 호출되는지에 대해 물어본다. 일단 주어진 피보나치 수열 함수가 있어서 그것을 이용하여 먼저 프로그래밍 해보았다.
#include <stdio.h>
#include <stdlib.h>
int fibonacci(int);
int num_0 = 0; int num_1 = 0;
int main(void) {
int num;
scanf("%d", &num);
int fibo_num;
int** array = (int**)malloc(sizeof(int*) * num); //가로 2, 세로 num인 동적배열 만들기
for (int i = 0; i < num; i++) {
array[i] = (int*)malloc(sizeof(int) * 2);
}
for (int i = 0; i < num; i++) {
num_0 = 0; num_1 = 0;
scanf("%d", &fibo_num);
fibonacci(fibo_num);
array[i][0] = num_0; array[i][1] = num_1;
}
for (int i = 0; i < num; i++) {
printf("%d %d\n", array[i][0], array[i][1]);
}
free(array[0]);
free(array);
return 0;
}
int fibonacci(int n) { //피보나치 수열
if (n == 0) { //0이 호출되었을 경우 전역 변수를 증가
num_0++;
return 0;
}
else if (n == 1) { //1이 호출되었을 경우 전역 변수를 증가
num_1++;
return 1;
}
else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
하지만 이렇게 작성하면 시간 초과가 떠버린다. 겉으로는 피보나치 수열의 가면을 하고 있지만, 실질적으로는 규칙을 구해서 풀어야 하는 문제였던 것이다.
각 수가 입력 받았을 때 0과 1이 호출되는 수는 다음 표와 같다:
0이 호출되는 횟수 1이 호출되는 횟수
0 0 1
1 1 0
2 1 1
3 1 2
4 2 3
5 3 5
6 5 8
2를 입력받았을 때 부터는 우리가 아는 피보나치 수열을 따라간다는 것을 볼 수 있겠다. 그러므로
만약 0이 입력되었을 경우 -> 0, 1을 출력한다
만약 1이 입력되었을 경우 -> 1, 0을 출력한다
그 이외의 수가 입력되었을 경우 -> 자신번째(?)의 피보나치 수와 (자신 - 1)번째의 피보나치 수를 출력한다
라는 조건으로 짜면 되겠다.
문제에서도 입력 숫자는 40 이하의 숫자라고 정해놓았기 때문에, 미리 40번째의 피보나치 수를 넣어놓은 배열을 이용한다.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int num;
scanf("%d", &num);
int array[41];
array[0] = 0; array[1] = 1; array[2] = 1;
for (int i = 3; i < 41; i++) {
array[i] = array[i - 1] + array[i - 2];
}
int a;
for (int i = 0; i < num; i++) {
scanf("%d", &a);
if (a == 0) {
printf("%d %d\n", 1, 0);
}
else if (a == 1) {
printf("%d %d\n", 0, 1);
}
else {
printf("%d %d\n", array[a - 1], array[a]);
}
}
}
문제를 푸는 것도 중요하지만, 효율적인 문제 풀이 방식을 찾는 것 또한 중요하다고 느낀 문제였다.
