백준 1003 피보나치 함수 (c++) : 피너클

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

1003번: 피보나치 함수

다이나믹을 이용했다.

그냥 피보나치 수열을 구하는것처럼 하면 된다. 3년전에 푼거여서 그런지 지금과는 스타일이 다르다.

int t;
int a[10000];

long long dp_i[41];
long long dp_j[41];

사용할 변수들이다.

t는 테스트케이스이고 a에는 테스트케이스에 입력하는 값들이 들어간다.

dp_i에는 0이 호출되는 횟수, dp_j에는 1이 호출되는 횟수가 들어간다.

cin >> t;
dp_i[0] = 1, dp_j[0] = 0;
dp_i[1] = 0, dp_j[1] = 1;
for (int i = 2; i < 41; i++) {
    dp_i[i] = dp_i[i - 1] + dp_i[i - 2];
    dp_j[i] = dp_j[i - 1] + dp_j[i - 2];
}

t를 입력받은뒤 dp들을 구한다.

dp_i는 0에 1번 출력되고 dp_j는 0에 1번 출력된다.

dp_i는 1에 0번 출력되고 dp_j는 1에 0번 출력된다.

이젠 피보나치 수열을 구하면 된다.

dp_i[2]에는 dp_i[1]과 dp_i[0]이 들어간다.

n이 2일때 0이 호출된 횟수는 n에 1일때와 0일때 호출된 횟수와 같다.

n이 3일때 0이 호출된 횟수는 n에 2일때와 1일때 호출된 횟수와 같다.

이걸 계속해서 반복하는 것이다.

for (int i = 0; i < t; i++) {
    cin >> a[i];
}
for(int i = 0; i < t; i++)
    cout << dp_i[a[i]] << " " << dp_j[a[i]] << endl;

그후 t만큼 a에 입력받고 

dp_i[a[i]]와 dp_j[a[i]]를 출력하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;


int main()
{
	int t;
	int a[10000];

	long long dp_i[41];
	long long dp_j[41];
	cin >> t;
	dp_i[0] = 1, dp_j[0] = 0;
	dp_i[1] = 0, dp_j[1] = 1;
	for (int i = 2; i < 41; i++) {
		dp_i[i] = dp_i[i - 1] + dp_i[i - 2];
		dp_j[i] = dp_j[i - 1] + dp_j[i - 2];
	}
	for (int i = 0; i < t; i++) {
		cin >> a[i];
	}
	for(int i = 0; i < t; i++)
		cout << dp_i[a[i]] << " " << dp_j[a[i]] << endl;
}

전체코드다.