1003) 피보나치 함수 (C++)

 출처 

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

1003번: 피보나치 함수

 내 풀이 

#include<iostream>

using namespace std;

int T = 0;

int dp_0[41];	//피보나치 0
int dp_1[41];	//피보나치 1

int main()
{
	dp_0[0] = 1;
	dp_0[1] = 0;

	dp_1[0] = 0;
	dp_1[1] = 1;

	for (int i = 2; i <= 40; i++)
	{
		dp_0[i] = dp_0[i - 1] + dp_0[i - 2];
		dp_1[i] = dp_1[i - 1] + dp_1[i - 2];
	}

	cin >> T;

	for (int i = 0; i < T; i++)
	{
		int x = 0;
		cin >> x;
		cout << dp_0[x] << " " << dp_1[x] << endl;
	}
}

 

 해설

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

최대 숫자가 40이므로 0과 1이 출력되는 배열을 41까지 잡고 40까지의 수를 for문을 이용하여 넣어준다.

 

 새로 안 것 

동빈나님의 다이나믹 프로그래밍 강의를 듣고 처음 풀어본 문제이다. 처음 봤을 때는 어떻게 풀어야할지 몰랐는데 강의를 듣고

중복되는 값들을 저장해나가면서 해야한다는걸 알았다.

 

다이나믹 프로그래밍 - 동빈나님 

https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6