프로그래머의 개발노트

[백준 1003] 피보나치 함수 (C++) 본문

백준 알고리즘

[백준 1003] 피보나치 함수 (C++)

7ULY 2021. 1. 21. 13:22


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


- 입력

첫째 줄에 테스트 케이스의 개수 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


저작자표시

'백준 알고리즘' 카테고리의 다른 글

[백준 1005] ACM Craft(C++)  (0) 2021.02.14
[백준 9095] 1,2,3 더하기 (C++)  (0) 2021.01.21
[백준 1463] 1로 만들기 (C++)  (0) 2021.01.21
[백준 17143] 낚시왕 (C++)  (0) 2021.01.20
[백준 1348] 주차장 (C++)  (0) 2021.01.17
'백준 알고리즘' Related Articles more
Comments