66. C++ 백준 1003 번 피보나치 함수 자세한 설명

안녕하세요 코딩하는 덕구입니다.

C++ 백준 1003 번 피보나치 함수입니다.

다이나믹 알고리즘 문제입니다.

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

1003번: 피보나치 함수

 

 

input N이 주어졌을 때 0, 1이 출력되는 횟수를 구해서 출력하는 문제입니다.

기본적인 전제입니다.

fibonacci(0)은 0을 출력하게 됩니다. (문제에 주어진 코드의 구현상)

fibonacci(1)은 1을 출력하게 됩니다. (문제에 주어진 코드의 구현상)

 

N이 2일 때 ( fibonacci(2)는 )

fibonacci(1),  fibonacci(2)를 호출하게 되고 

fibonacci(1)의 출력 1, fibonacci(0)의 출력 0

즉 fibonacci(2)는 1을 1번 출력하고, 0을 1번 출력하게 됩니다.

 

그럼 fibonacci(3)은 어떻게 될까요?

fibonacci(3) = fibonacci(2) + fibonaci(1) 

fibonacci(2)는 방금 구했죠, 1을 1번 0을 1번

fibonacci(1)은 문제에 주어졌습니다. 1을 1번 0을 0번

fibonacci(3) 은 1을 2번, 0을 1번

즉 fibonacci(3)의 1과 0이 등장한 횟수는

fibonacci(2)에서 등장한 1과 0의 횟수 +  fibonacci(1)에서 등장한 1과 0의 횟수라는 것을

알 수 있습니다.

위와 같은 방법으로 접근하여 코드를 구현해 봅시다.

 

각 index별 0이 등장한 횟수, 1이 등장한 횟수를 담는 배열을 선언합니다.

input N은 최대 40까지이고, 0일때의 값, 1일때의 값만 저장하면 되므로 아래와 같이 공간을 할당합니다.

int arr[41][2] = {0,};

 

 0과 1의 fibonacci 함수에서의

0이 출력되는 횟수, 1이 출력되는 횟수입니다.

문제에서 주어진 초기 값 입니다.

arr[0][0] = 1; arr[0][1] = 0; //N이 0일때 0은 1번, 1은 0번 출력
arr[1][0] = 0; arr[1][1] = 1; //N이 1일때 0은 0번, 1은 1번 출력

 

input N의 0과 1이 등장한 횟수가 배열에 있는지 체크를 하고

만약 있다면 0이 등장한 횟수, 1이 등장한 횟수를 출력합니다.

if ( N <= len ) cout << arr[N][0] << " " << arr[N][1] << endl;

 

만약 없다면 없는 숫자부터 N까지

0이 등장한 횟수, 1이 등장한 횟수를 구해서 차례대로 채우고 난 후

input N의 0이 등장한 횟수, 1이 등장한 횟수를 출력합니다.

else{
    for (int n = len + 1; n <= N; n++){
        arr[n][0] = arr[n-1][0] + arr[n-2][0];
        arr[n][1] = arr[n-1][1] + arr[n-2][1];
    }
    cout << arr[N][0] << " " << arr[N][1] << endl;
}

 

C++ 백준 1003 번 최종 코드입니다.

#include <iostream>
using namespace std;
int arr[41][2] = {0,};

int main(){
    int T, N, len = 1;
    cin >> T;
    arr[0][0] = 1; arr[0][1] = 0; //N이 0일때 0은 1번, 1은 0번 출력
    arr[1][0] = 0; arr[1][1] = 1; //N이 1일때 0은 0번, 1은 1번 출력

    for(int t = 0; t<T; t++){
        cin >> N;
        if ( N <= len ) cout << arr[N][0] << " " << arr[N][1] << endl;
        else{
            for (int n = len + 1; n <= N; n++){
                arr[n][0] = arr[n-1][0] + arr[n-2][0];
                arr[n][1] = arr[n-1][1] + arr[n-2][1];
            }
            cout << arr[N][0] << " " << arr[N][1] << endl;
        }
    }
    return 0;
}

 

C++ 백준 1003 번 피보나치 함수이었습니다. 감사합니다.