백준 알고리즘
[백준 1003] 피보나치 함수 (C++)
7ULY
2021. 1. 21. 13:22
- 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
- 출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
- 풀이
문제에 피보나치 함수에 대한 코드가 주어져 있는데,
f(n) = f(n - 1) + f(n - 2)
위의 식을 잘 생각해보면 Base Case인
if(n == 0)
return (0);
else if (n == 1)
return (1);
이 부분을 만날 때 까지 저 식을 타고 타고 들어간다고 생각해 보면 됩니다.
n = 3 일 경우를 예시로 들어보면,
f(3) = f(2) + f(1)
이고,
f(2) = f(1) + f(0)
f(1) = 1
f(0) = 0
이므로, f(0) 일 때는 0이 1번, 1이 0번이고, f(1) 일 때는 0이 0번, 1이 1번이 나옵니다.
따라서 f(2)에서 0은 (f(1)에서 계산한 0이 나오는 횟수 + f(0)에서 계산한 0이 나오는 횟수)횟수 만큼 출력이 되고, 1은 (f(1)에서 계산한 1이 나오는 횟수 + f(0)에서 계산한 1이 나오는 횟수)횟수 만큼 출력이 됩니다.
이제 f(3)으로 올라와 보면 0은 (f(2)에서 계산한 0이 나오는 횟수 + f(1)에서 계산한 0이 나오는 횟수)횟수 만큼 출력하는 것임을 알 수 있고, 1은 (f(2)에서 계산한 1이 나오는 횟수 + f(1)에서 계산한 1이 나오는 횟수)횟수 만큼 출력됨을 알 수 있습니다.
- 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <iostream> #include <vector> #define endl "\n" std::vector<std::pair<int, int> >dp; int T; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> T; } void solve() { int N; std::cin >> N; std::cout << dp[N].first << " " << dp[N].second << endl; } void make_val() { int i = 1; dp.resize(41); dp[0] = {1, 0}; dp[1] = {0, 1}; while(++i <= 40) { dp[i].first = dp[i - 1].first + dp[i - 2].first; dp[i].second = dp[i - 1].second + dp[i - 2].second; } } int main() { input(); make_val(); while(T--) solve(); return (0); } | cs |