[BOJ] 1003 - 피보나치 함수

안녕하세요.

여행벌입니다.

문제는 단순하지만, 0.25초라는 짧은 제한 시간 때문에 DP를 이용해야만 풀 수 있는 문제입니다.

---

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

1003번: 피보나치 함수

[알고리즘설계]

fibonachi(N)을 구하는데, fibonachi(1), fibonachi(0)이 몇 번 호출되는지 구하기 위해서는

fibonachi(N-1), fibonachi(N-2)를 구하는데 fibonachi(1), fibonachi(0) 이 몇 번 호출되는지 알고있으면 해결됩니다.

2차원 DP배열[2][N]을 다음과 같이 정의합니다.

DP[0][i] : fibonachi(i)를 구하는데 fibonachi(0) 의 호출 횟수.

DP[1][i] : fibonachi(i)를 구하는데 fibonachi(1) 의 호출 횟수.

그러면 아래와 같은 방정식이 성립합니다.

DP[0][i+1] = DP[0][i] + DP[0][i-1]

DP[1][i+1] = DP[1][i] + DP[1][i-1]

#include<iostream>

using namespace std;

int call_list[2][41]; // fibonachi(n)에 대해서 0이 호출되는 횟수를 0행, 1이 호출되는 횟수를 1행에 저장한다.


int main(void) {
	call_list[0][0] = 1;
	call_list[1][1] = 1;
	int total_case;
	cin >> total_case;
	while(total_case>0){
		int input;
		cin >> input;
		for (int i = 2; i <= 40; i++) {
			call_list[0][i] = call_list[0][i - 1] + call_list[0][i - 2];
			call_list[1][i] = call_list[1][i - 1] + call_list[1][i - 2];
		}
		cout << call_list[0][input] << " " << call_list[1][input];
		if(total_case != 1)
			cout << endl;
		total_case--;
	}
}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.