[C언어] 백준 1003 : 피보나치 함수

백준 1003 : 피보나치 함수

 

문제 링크

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

1003번: 피보나치 함수

 

 

문제 내용

(요약) 위 함수는 피보나치 수열에서 사용된 0과 1을 출력하는 함수이다.

N이 주어졌을 때, fibonacci(n)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

 

Idea

해당 문제에 대한 접근은 이 역시 피보나치 수열을 활용한다고 보면 된다.

 

이 문제를 풀기전에 아래 기본적인 피보나치 수열에 대한 문제를 풀고오면 좋다.

https://wtg-study.tistory.com/4

[JAVA] 백준 2748 : 피보나치 수 2

 

피보나치 수열의 점화식은 아래와 같다.

Fn = Fn-1 + Fn-2 ( n>=2 )

이를 고려하여 구하고자 하는 문제의 규칙을 잘 생각해 보자.

 

	0	1
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3

표를 잘 살펴보면 fibo(2)는 fibo(1)과 fibo(0)의 합임을 알 수 있다.위의 표는 n번째에서 출력되는 0과 1의 개수를 보여준다.

마찬가지로,

fibo(3) = fibo(2) + fibo(1)

fibo(4) = fibo(3) + fibo(2)

 

즉, 이것을 배열로 표현한다면

fibo[n][0] = fibo[n-1][0] + fibo[n-2][0] (n>=2, 0의 개수를 구하는 연산)

fibo[n][1] = fibo[n-1][1] + fibo[n-2][1] (n>=2, 1의 개수를 구하는 연산)

 

 

Code

#include <stdio.h>
 
int main(){
    int T,N,fibo[41][2];
    scanf("%d",&T);
 
    //0번째, 0의 개수 = 1, 1의 개수 = 0
    fibo[0][0]=1; fibo[0][1]=0;
 
    //1번째, 0의 개수 = 0, 1의 개수 = 1
    fibo[1][0]=0; fibo[1][1]=1;
 
    //0과 1의 개수를 구하는 피보나치 수열
    for(int i=2;i<=40;i++){
        fibo[i][0]=fibo[i-1][0]+fibo[i-2][0];
        fibo[i][1]=fibo[i-1][1]+fibo[i-2][1];
    }
    
    //T개의 테스트 케이스
    while(T--){
        scanf("%d",&N);
        printf("%d %d\n",fibo[N][0],fibo[N][1]);
    }
    return 0;
}