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

문제링크 https://www.acmicpc.net/problem/1003

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

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

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

 

 

 

 

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

 

1003_피보나치 함수

 

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1 복사

3
0
1
3

예제 출력 1 복사

1 0
0 1
1 2

예제 입력 2 복사

2
6
22

예제 출력 2 복사

5 8
10946 17711

 

 

내 제출

#include <iostream>

using namespace std;
int count0 = 0;
int count1 = 0;
int pre1 = 1, pre2 = 0;

void fibo(int a) {
	int pre0 = 1;
	int pre00 = 0;
	int pre1 = 1;
	int pre11 = 1;

	if (a == 0) {
		count0++;
	}
	else if (a == 1) {
		count1++;
	}
	else if (a == 2) {
		count0 = pre0;
		count1 = pre1;
	}
	else {
		for (int i = 3;i <= a;i++) {
			count0 = (pre0 + pre00);
			count1 = (pre1 + pre11);
			pre00 = pre0;
			pre0 = count0;
			pre11 = pre1;
			pre1 = count1;
		}
	}
}

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

	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		int a;
		cin >> a;
		fibo(a);
		cout << count0 << " " << count1 << "\n";
		count0 = 0;
		count1 = 0;
	}
}

 

0과 1은 미리 정의를 해줬고 2도 추가적으로 답을 정의해줬다.

3부터는 이전의 0개수와 1개수를 더해 출력해주었다.

fibonacci(3) = fibonacci(2) + fibonacci(1) 인데 이때 발생한 0의 개수와 1의 개수는 각각 2와 1에서 발생한 0의 개수 합, 1의 개수 합과 같다. 이를 fibo 함수에 구현하고 fibo함수를 main함수에서 호출하는 방식을 이용했다.

fibo함수 안에서는 이전 0의 개수들을 pre0, pre00에 각각 저장하고 1의 개수들은 pre1, pre11에 가각 저장하여 이를 더하고 count0(0의 개수)와 count1(1의 개수)에 대입하였다.

이때 count0과 count1을 전역변수로 선언하여 따로 값을 리턴해주지 않고 사용하였다.

반응형