백준 1003번 피보나치 함수

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

 

피보나치 함수 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.25 초 (추가 시간 없음)

128 MB

228663

71696

56750

33.548%

문제

다음 소스는 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

 

---

 

풀이법 :

동적 계획법(DP)을 통하여 각 숫자마다 피보나치 수열을 통해 몇 번의 0과 몇 번의 1을 출력하는지 map을 통하여 저장한다.

1. 피보나치 수열을 사용하는 과정에서 map에 해당 숫자 데이터가 있는지 확인한다.

2. 있다면 해당 데이터를 불러와 사용하며, 없다면 피보나치 수열을 통하여 계산한 후 이를 map에 추가한다.  

 

#include <iostream>
#include <map>

using namespace std;

struct dim
{
	long long int one;
	long long int zero;

	dim()
	{
		one = 0;
		zero = 0;
	}

	dim(int _one, int _zero)
	{
		one = _one;
		zero = _zero;
	}
};

long long int fibonacci(int n, long long int& OuterOne, long long int& OuterZero, map<int,dim>& m)
{
	if (m.find(n) != m.end())
	{
		OuterOne += m[n].one;
		OuterZero += m[n].zero;
		return 0;
	}

	int tmp;

	if (n == 0)
	{
		OuterZero++;
		return 0;
	}
	else if (n == 1)
	{
		OuterOne++;
		return 1;
	}
	else
	{
		tmp = fibonacci(n - 1, OuterOne, OuterZero, m) + fibonacci(n - 2, OuterOne, OuterZero, m);
		m.insert(pair<int, dim>(n, dim(OuterOne, OuterZero)));
	}

	return tmp;
}

int main()
{
	int count = 0;
	cin >> count;

	map<int, dim> m;

	for (int i = 0; i < count; i++)
	{
		int tmp;
		cin >> tmp;

		if (m.find(tmp)!=m.end())
		{
			cout << m[tmp].zero << " " << m[tmp].one << "\n";
			continue;
		}

		long long int One = 0;
		long long int Zero = 0;

		fibonacci(tmp, One, Zero, m);
		m.insert(pair<int, dim>(tmp, dim(One, Zero)));
		cout << Zero << " " << One << "\n";
	}
	
	return 0;
}