백준 1003 _ 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

---

✨ 내 소스 코드

#include<iostream>
using namespace std;
int memo[41][2] = { {1,0},{0,1} };//{0개수, 1개수}

void fibo() {
	for (int i = 2; i < 41; i++) {
		memo[i][0] = memo[i - 1][0] + memo[i - 2][0];
		memo[i][1] = memo[i - 1][1] + memo[i - 2][1];
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int num, n;
	fibo();
	cin >> num;
	while (num--) {
		cin >> n;
		cout << memo[n][0] << " " << memo[n][1]<<endl;
	}
	return 0;
}

 

🙏 문제 풀이

fibo(2) = fibo(1)+fibo(0)

fibo(3) = fibo(2)+fibo(1)

fibo(4) = fibo(3)+fibo(2)

...

위와 같이 fibo(n) = fibo(n-1)+fibo(n-2) 이다

 

이를 이용해서 fibo(2)의 0개수는 fibo(1)의 0개수 + fibo(0)의 0개수

fibo(3)의 0개수는 fibo(2)의 0개수 + fibo(1)의 0개수

fibo(4)의 0개수는 fibo(3)의 0개수 + fibo(2)의 0개수

와 같이 계산을 한다

1의 개수도 마찬가지로 계산을 한 뒤, 원하는 N의 0개수와 1개수를 출력한다

 

간단한 DP 문제였다

 

⭐ 문제 풀이 결과