[백준 / BOJ] - 1003번 피보나치 함수 C++

---

 

백준 - 단계별로 풀어보기 [1003] 

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

 

문제

 

 

풀이

 

규칙성을 찾는것이 중요한 문제이다.

 

N = 0, 1 0
N = 1, 0 1

N = 2, 1 1

N = 3, 1 2

N = 4, 2 3

 

여기서 알 수 있는 규칙성은 무엇일까? 0이 출력되는 횟수와 1이 출력되는 횟수를 각각 두고 봐보자.

0의 출력 횟수 1, 0, 1, 1, 2, 3, ...

1의 출력 횟수 0, 1, 1, 2, 3, 5, ...

 

0의 출력횟수는 맨앞은 N이 0일때는 1이고 1부터는 0부터 시작하는 피보나치 수열이며

1의 출력횟수는 N이 0일때 부터 시작하는 피보나치 수열이다.

 

따라서 본 문제는 피보나치 수열을 DP로 구하는 코드를 그대로 사용하여 풀 수 있다.

 

 

코드

 

#include <iostream>
using namespace std;
long long fiboarr[50] = {0,1,};
long long fibo(int N)
{
    if(N == 0 || N == 1)
        return fiboarr[N];
    else if(fiboarr[N] == 0)
        fiboarr[N] = fibo(N-1) + fibo(N-2);
    return fiboarr[N];
}
int main() {
    int T;
    cin >> T;
    int tmp;
    for(int i = 0; i < T; i++)
    {
        cin >> tmp;
        if(tmp == 0)
            cout << "1 0" << '\n';
        else
            cout << fibo(tmp-1) << ' ' << fibo(tmp) << '\n';
    }
}

 

 

평가

 

규칙성을 찾으면 풀 수 있는 문제이다.

앞에서 만들었던 DP로 피보나치 수열 풀기 코드를 활용하여 fibo(N-1)과 fibo(N)을 출력해주면 답을 얻을 수 있다.