[C++] 백준 온라인 저지 1003번 피보나치 함수 풀이

피보나치 함수에서 0과 1이 출력되는 횟수를 구하는 문제 

 

---

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

1003번: 피보나치 함수

 

 

문제의 조건

 

 다음은 N번째 피보나치 수를 구하는 C++ 함수이다. 

 

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

 fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

 위 과정의 결과로 1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력하기 

 

풀이 과정

 

 피보나치 함수가 DP의 대표적인 예제였고 점화식으로 이루어져 있으며 DP에서 중요한 것은 점화식을 잘 세우는 것이었기 때문에...!

 이 문제도 점화식을 잘 세우면 풀릴 것 같았습니다. 처음으로 구글링 없이 점화식을 세워 봄! ㅋㅋㅋ(전 수포자였거든요...)

 

테스트 케이스	정답(0 출력횟수 1 출력횟수)
0	1 0
1	0 1
2	1 1
3	1 2

 

 피보나치 함수를 보면 2보다 크거나 같으면 fibonacci(n-1) + fibonacci(n-2)를 호출합니다. 여기에서 점화식을 세우기 위한 아이디어를 얻을 수 있습니다. 그러고나서 예제를 보면 0과 1은 기저 조건으로 설정되어 있고 2는 0과 1의 횟수들을 각각 더한 것이라는 것을 알 수 있습니다. 그리고 3은 3에서 1을 뺀 2와 2를 뺀 1의 횟수를 각각 더한 것이라는 것을 알 수 있습니다. 

 

 피보나치 함수에서 얻은 아이디어와 예제에서의 규칙을 합치면 N의 0과 1 출력횟수를 얻기 위해서는 

0 출력횟수 = arr[n-1]의 0 출력횟수 + arr[n-2]의 0 출력횟수

1 출력횟수 = arr[n-1]의 1 출력횟수 + arr[n-2]의 1 출력횟수

라는 점화식을 도출할 수 있습니다. 

 

 이 점화식을 코드로 옮기기만 하면 이 문제의 답은 쉽게 구할 수 있었습니다. 

 

코드 작성 과정

1. 문제에서 N은 40보다 작거나 같은 자연수 또는 0이라고 했으므로 숫자 40까지 저장할 수 있는 배열을 만든다. 그런데 0과 1 출력횟수를 각각 답으로 출력해야 하기 때문에 각 배열 인덱스에는 2칸짜리 배열이 들어가도록 하는 2차원 배열로 만든다.(arr[40][2]) 이 때 숫자 40의 0과 1 출력횟수를 저장하려면 40번째 인덱스에 접근할 수 있어야 하기 때문에 총 배열 길이는 40+1이 되어야 함(arr[41][2])

 

2. 0과 1에 대해서는 기저조건으로 설정해 놓는다. 

 

3. 아까 도출했던 점화식을 반복문을 이용해서 배열의 2 ~ 40번째 인덱스까지 각각 0과 1 출력횟수를 저장한다. 

 

4. 테스트 케이스들을 입력받아서 각 인덱스에 저장된 횟수들을 출력한다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX_NUM = 40;
int main(int argc, const char * argv[])
{
    vector<vector<int>> counts(MAX_NUM + 1, vector<int>(2, 0));
    counts[0][0] = 1; //0과 1 기저조건 설정 
    counts[0][1] = 0;
    counts[1][0] = 0;
    counts[1][1] = 1;
    
    for (int i = 2; counts.size() > i; i++)
    {
        //각 숫자별로 횟수 세팅 
        counts[i][0] = counts[i-1][0] + counts[i-2][0];
        counts[i][1] = counts[i-1][1] + counts[i-2][1];
    }
    
    int T;
    cin >> T;
    
    for (int i = 0; T > i; i++)
    {
        int N;
        cin >> N; //테스트 케이스 입력받아서 해당 인덱스에 저장된 값 출력 
        cout << counts[N][0] << " " << counts[N][1] << endl;
    }
    
    return 0;
}