이번 문제는 백준(boj) 1003번 피보나치 함수 코드 입니다.
문제 : https://www.acmicpc.net/problem/1003
달콤하게 그냥 복붙 하면 되는거 아니야? 라고 생각 하실 수도 있는 유혹의 문제에요..
풀이
다이나믹 프로그래밍 문제인 만큼 규칙을 찾는게 중요합니다.
0 = 0
1 = 1
2 = 1 + 0
3 = 2 + 1
4 = 3 + 2
5 = 4 + 3
이런식으로 진행이 됩니다.
결과적으로 단순히 앞에꺼 + 앞에 앞에꺼 더해주면 되는 겁니다.
이런식으로 문제에 주어진 범위인 40까지 채워주고 시작 하면 됩니다!.
(전 여기서 한단계 더 규칙을 찾아서 간략화 했지만 굳이 저처럼 하실 필요 없이
f(n) = f(n-1) + f(n-2) 로 하시면 됩니다.
코드
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int main() {
int n;
int t;
vector<vector<int>> fibo(41,vector<int>(2));
fibo[0][0] = 1;
fibo[0][1] = 0;
for (int i = 1; i < 41; i++) {
fibo[i][0] = fibo[i - 1][1];
fibo[i][1] = fibo[i - 1][1] + fibo[i - 1][0];
}
cin >> n;
for (int i = 0; i < n; i++) {
scanf(" %d", &t);
cout << fibo[t][0] << " " << fibo[t][1] << "\n";
}
return 0;
}