[BOJ] 1003번 : 피보나치 함수

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;

int t; 
vector<pair<int,int>> d(42,{0,0}); // {0 cnt, 1 cnt};

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t; 
	while (t--) {
		int n;
		cin >> n; 
		d[0] = { 1,0 }, d[1] = { 0,1 }; 
		for (int i = 2; i <= n; i++) {
			d[i].first = d[i - 1].first + d[i - 2].first; 
			d[i].second = d[i - 1].second + d[i - 2].second;
		}
		cout << d[n].first << ' ' << d[n].second << '\n';
	}
}

 

 

3. solution 2 :

// Authored by : heheHwang
// Co-authored by : -
// http://boj.kr/0a669ebf1000436b94e3067bdda26575
#include <bits/stdc++.h>
using namespace std;

int fibo[42][2];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  fibo[0][0] = 1;
  fibo[1][1] = 1;
  for (int i = 2; i <= 40; i++) {
    fibo[i][0] = fibo[i - 1][0] + fibo[i - 2][0];
    fibo[i][1] = fibo[i - 1][1] + fibo[i - 2][1];
  }
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    cout << fibo[N][0] << " " << fibo[N][1] << endl;
  }
}
/*
1. 테이블 정하기
fibo[i][k] = 숫자 i가 k(0 or 1)를 호출한 횟수
2. 점화식 찾기
fibo[i][k] = fibo[i - 1][k] + fibo[i - 2][k]
3. 초기값 정하기
fibo[0][0] = 1, fibo[1][1] = 1
*/

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/1003.cpp

basic-algo-lecture/0x10/solutions/1003.cpp at master · encrypted-def/basic-algo-lecture