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

1. 문제이해

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

 

주어진 피보나치 함수를 호출했을 때, 0과 1이 각각 몇번 출력되는지를 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

실버 3문제인데 너무 쉬운거 아닌가? 라는 생각은 역시나 오산이었다.

문제에 주어진 피보나치 함수를 응용해 구현했더니 바로 시간 초과가 났다.

아마 이 글을 보고 계신 분들의 대부분이 시간초과로 인한 오류로 찾아보고 계시지 않을까..

하고 조심스레 예측해본다. 🧐

 

시간초과를 방지하는 방법으로 나는 피보나치 수열의 원리를 적용했다.

피보나치 수열의 원리는 다음과 같다.

 

출처 : 피보나치 수열 알고리즘 (aerocode.net)

 

피보나치 수열에서, fibonacci(N)의 N이 1보다 클 경우 (2 이상인 경우),

다음과 같은 원리를 적용받게 된다.

 

0과 1의 개수도 동일하다.

fibonacci(N)의 0의 개수는 fibonacci(N-1)의 0의 개수 +  fibonacci(N-2)의 0의 개수와 동일하며,

1의 경우에도 마찬가지이다.

 

이를 코드에 적용시켜 문제를 풀었더니 시간초과가 해결되었다.🤗

시간초과가 난 코드도 부끄럽지만 밑의 소스코드에 같이 게시해두었다.

 

 

 

3. 소스코드

 

1. 주어진 함수를 응용하여 풀이 (시간초과)

#include <iostream>
#include <stdio.h>
using namespace std;
int count0 = 0;	// 0이 출력되는 횟수
int count1 = 0;	// 1이 출력되는 횟수

// 피보나치 함수
// (백준에서 주어진 함수에 count0++, count1++만 추가)
int fibonacci(int n) {
	if (n == 0) {
		//printf("0");
		count0++;	// 0의 개수 count
		return 0;
	}
	else if (n == 1) {
		//printf("1");
		count1++;	// 1의 개수 count
		return 1;
	}
	else {
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

int main() {
	int T;	// 테스트 케이스의 개수
	int testcase[10000];

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> testcase[i];
		fibonacci(testcase[i]);
		cout << count0 << " " << count1 << endl;
		count0 = 0;
		count1 = 0;
	}

	return 0;
}

백준에서 주어진 코드를 응용해 만든 코드이다.

기존 코드의 printf 구문 대신, 해당 숫자를 카운트하는 구문으로 바꾸어주고,

메인함수의 for문을 통해 바로 출력을 하는 형태로 구현해주었다.

위의 방식은 앞서 이야기했듯, 백준에서는 시간초과가 발생했다.

 

 

2. 피보나치 함수의 원리를 이용한 코드 (성공)

#include <iostream>
using namespace std;

int main() {
	int T;	// 테스트 케이스의 개수
	int N;	// 각 테스트 케이스, fibonacci(N)

	// 피보나치 함수의 0, 1의 개수 저장
	// fibonacci[a][b]에서, a는 몇번째 함수인지
	// b는 0의 개수인지 1의 개수인지를 뜻함
	int fibonacci[42][2];

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// 피보나치 수열 값 초기화
	// fibonacci(0)의 0값은 1, fibonacci(0)의 1값은 0
	fibonacci[0][0] = 1; 
	fibonacci[0][1] = 0;
	// fibonacci(1)의 0값은 0, fibonacci(1)의 1값은 1
	fibonacci[1][0] = 0;
	fibonacci[1][1] = 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];
	}

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		cout << fibonacci[N][0] << " " << fibonacci[N][1] << endl;
	}

	return 0;
}

피보나치 함수의 원리를 이용해 코드를 새롭게 구현했다.

이중 배열을 통해, 해당 피보나치 수열의 0과 1의 개수를 각각 저장 후 더해주는 방식을 사용했다.

fibonacci[a][b]에서, a는 몇번째 함수인지, b는 0의 개수인지 1의 개수인지를 뜻하며

위 규칙을 기준으로 값들을 초기화 해주었다.

 

또한, 피보나치 수열의 원리는 N이 2일때부터 적용가능하므로,

for문도 2일때부터 적용시켜주었다.

 

 

---

생각없이 주어진 함수를 통해 구현하려 했다가

역시나 시간초과의 뜨거운 맛을 보게되었다...😱

백준에서 시간초과나 에러가 뜨면 왜 그렇게 화가 나는지...ㅎㅎ

SQLD 시험도 끝났고.. 화이자 백신도 2차까지 다 맞아서 이틀을 쉬었는데,

쉰 만큼 내일부터는 다시 열심히 달려야지💪💪