BaekJoon 1003 피보나치 함수

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

소스결과 1984 KB / 8 ms

출처 Backjoon 

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

문제에 나와 있는 소스 코드를 기반으로 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 )

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

 

알고리즘

1. DP Table을 초기화 시킨다.

2. 들어온 값에 대하여 DP Table의 값을 출력해준다.

 

소스코드

#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;
}