[백준] 1003 피보나치 함수 - C

 

 

https://www.acmicpc.net/problem/1003

 

---

 

n번째 피보나치 수를 구하는 과정 중에 도달하는(문제 내에서는 "출력되는" 이라고 표현함)

0과 1의 갯수를 세는 문제이다.

 

각 피보나치 수의 0과 1의 갯수에 대한 규칙을 찾도록 하자. (약간의 노가다)

 

n번째 피보나치 수에서 도달하는 1의 갯수는 n번째 피보나치 수와 같다.

ex) 6번째 피보나치 수(=8)에서 도달하는 1의 갯수 = 8

 

n번째 피보나치 수에서 도달하는 0의 갯수는 n-1번째 피보나치 수와 같다.

ex) 8번째 피보나치 수(=21)에서 도달하는 0의 갯수 = 7번째 피보나치 수 = 13

 

위의 규칙을 활용하여 코드를 짰다.

#include <stdio.h>

int fib(int n) {
	if (n <= 1) {
	return n;
	}
	return fib(n - 1) + fib(n - 2);
}

int main() {

	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
	int n;
	scanf("%d", &n);

	printf("%d %d\n", fib(n - 1), fib(n));
	}
}

 

코드의 결과 자체는 맞으나 39같은 큰 값을 입력하게 되면 문제의 시간 제한인 0.25초를 넘기게 된다.

 

불필요한 함수 호출을 줄이고 실행시간을 단축시키기 위해 메모이제이션 기법을 사용하였다.

#include <stdio.h>

int memo[45];

int fib(int n) {
	if (n <= 1) {
		if (n == -1) {
			return 1;
		}
		return n;
	}
	int result;
	int index = n - 2;
	if (memo[index]) { //이미 계산된 값이 있다면...
		result = memo[index];
	}
	else { //계산된 값이 없다면... => 계산해야한다
		memo[index] = fib(n - 1) + fib(n - 2);
		result = memo[index];
	}
	return result;
}

int main() {

	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		int n;
		scanf("%d", &n);
		printf("%d %d\n", fib(n - 1), fib(n));//0과 1의 갯수에 대한 규칙
	}
}

 

 

이 기법을 사용해 한번 계산한 피보나치 수는 배열에 저장해놓고,

값이 필요할때마다 함수를 호출하는게 아니라 배열에서 꺼내 쓰도록 하였다.

이를 통해 불필요한 연산을 줄여 실행시간을 단축시킬 수 있다.

 

---