1003번 피보나치, 다이나믹 프로그래밍 [1]

표준 입출력 => std 네임스페이스 안에 존재한다.

include <iostream>

std 전체 네임스페이스 사용은 바람직하지 않기 떄문에 각각 선언

using std::cin;

using std::cout;

---

피보나치는 반복되는 재귀 알고리즘인데 반복되면 시간이 오래걸려 시간초과가 뜬다.

시간초과를 줄이기 위해 다이나믹 프로그래밍 기법을 이용하여 한번 계산한것은 다시 계산하지 않게 한다.

그리고 이미 존재하는 값을 원하면 바로 배열에서 꺼내와서 계산 없이 출력한다.

---

int main()
{
	int num;
	int n;
	scanf("%d", &num);
	int dp[2][41] = { 0, };
	dp[0][0] = 1;
	dp[1][0] = 0;
	dp[0][1] = 0;
	dp[1][1] = 1;
	//cin >> num;

	for (int i = 2; i < 41; i++) {
		dp[0][i] = dp[0][i - 1] + dp[0][i - 2];
		dp[1][i] = dp[1][i - 1] + dp[1][i - 2];
	}
	for (int i = 0; i < num; i++) {
		//cin >> n;
		scanf("%d", &n);
		//fibonacci(n);
		/*cout << zero << " " << one << std::endl;*/
		printf("%d %d\n", dp[0][n], dp[1][n]);
		//printf("%d %d\n", zero, one);
	}

}