[BOJ] 1003 피보나치 함수

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

Note

문제에 나와 있는 소스 코드를 기반으로 0이 출력되는 경우와 1이 출력 되는 경우의 수를 출력하는 문제

저 함수를 직접 코드화 시켜서 printf 문 대신 0 인덱스를 1씩 추가시키면 시간 초과의 늪으로 들어간다
테스트 케이스 범위도 좁은 만큼 시간 제한도 0.25초로 매우 빡세다

점화식을 세우기 위해 0부터 4까지 계산해보면
0 : 1 0
1 : 0 1
2 : 1 1
3 : 1 2
4 : 2 3
이라는 결과를 바탕으로 0 이 출력되는 경우의 수와 1이 출력되는 경우의 수에 대해서 피보나치 수열처럼 구현하면 된다.
따라서 점화식은

dpTable[i] = dpTable[i-1] + dpTable[i-2] ( 단 i > 1 )

위 점화식을 바탕으로 소스코드를 작성하자

소스코드

#include <iostream>

using namespace std;

const int MAX = 40;

int main()
{
	int tcc;
	int zeroTable[MAX + 1] = { 1, };
	int oneTable[MAX + 1] = { 0 , 1 };

	cin >> tcc;

	for (int i = 2; i < MAX + 1; i++)
	{
		zeroTable[i] = zeroTable[i - 1] + zeroTable[i - 2];
		oneTable[i] = oneTable[i - 1] + oneTable[i - 2];
	}

	for (int i = 0; i < tcc; i++)
	{
		int n;
		cin >> n;

		cout << zeroTable[n] << ' ' << oneTable[n] << '\n';
	}

	return 0;
}

2019-01-14 10:00:00에 Tistory에서 작성되었습니다.