피보나치 수열 3 (feat. 백준 1003 피보나치 함수)

 

1. 필요한 개념

Dynamic Programming 

https://m-falcon.tistory.com/118

피보나치 수열 2 (Memoization, Dynamic Programming ver)

2. 문제

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

1003번: 피보나치 함수

 

3. 핵심 Point

문제에서 요구하는 것은

피보나치 재귀함수 구현에서

0이 출력되는 갯수 와 1이 출력되는 갯수를 출력하는 것인데 순서쌍으로 표현해보자.

 

n번째 피보나치수	0 출력 개수	1 출력 개수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13

 

규칙이 보이지 않는가?

1의 출력 갯수는 기존 N번째 피보나치 수열의 수를 구하는 문제와 일치한다.

0의 출력 갯수는 N 입력시 N-1번째 피보나치 수열의 수이다.

단, 0 출력 개수 중 0과 1에서 예외가 발생한다.

0의 경우 0출력 갯수가 1, 1출력 개수가 0

1의 경우 0출력 갯수가 0, 1출력 개수가 1 이므로 예외처리가 필요하다.

 

제한 시간을 보면 알겠지만, 재귀를 통해 구현하면 시간초과가 발생하기 쉽다.

따라서 지난 포스팅인 Dynamic Programming 기법을 활용해 

시간 복잡도를 낮추는 방법을 채택했다.

 

4. 구현

#include <iostream>
using namespace std;

// 전역변수 선언 
int arr[101] = {0};

//Dynamic Programming
int fibo(int n){
    arr[0] = 0; // 0번째 피보나치 수는 0 
    arr[1] = arr[2] = 1; // 1,2 번째 피보나치 수는 1 
     for(int i = 3; i <= n; i++) // 3부터는 이전 값을 재활용 
     arr[i] = arr[i-1] + arr[i-2];
    
    return arr[n];
}

int main(void){
    int TestNum, n, zeroCount, oneCount;
    //zeroCount: 0출력 개수, oneCount: 1출력개수  
    cin >> TestNum;
    for(int i = 1; i <= TestNum; i++)
    {
        cin >> n;
        if(n == 0){
            zeroCount = 1; // 0번째 수일 경우 0출력 개수 1 
        } else if (n == 1){
            zeroCount = 0; // 1번째 수일 경우 0출력 개수 0 
        }
        else { // 그 외의 경우 0출력 개수는 n-1번째 수를 구한 값과 같음 
            zeroCount = fibo(n-1);
        }
        oneCount = fibo(n); // 1의 출력 개수는 n번째 피보나치 수와 같음. 
        
        cout << zeroCount << ' ' << oneCount << endl;
    }
    return 0;
    
}

 

상세하게 주석을 달아놓았으니 읽다보면 저절로 이해가 될 것이다.

컴퓨터 앞에서 무작정 코딩을 시작하기 전에

노트에다가 0출력, 1출력 개수를 순서쌍으로 표현해보니 규칙이 쉽게 보였다.

 

손코딩의 중요성을 느끼는중이다.