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

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

1003번: 피보나치 함수

 

난이도: solved.ac 실버 3

 

 

 

 

피보나치 수열은 dp(다이나믹 프로그래밍, 동적 계획법)를 이용하면 매우 빠르게 n번째 수열을 구할 수 있다

이번 문제는 n번째 수열을 찾는 게 아니라 f(0)과 f(1)을 몇 번 호출하는지 구하는 문제이다

이것도 dp를 이용해 금방 구할 수 있다

일단 n = 0일 때는 f(0)을 1번 출력하고 f(1)을 0번 출력한다

이를 2차원 배열로 나타내보자

f[n][0]은 n번째 피보나치 수열의 f(0)을 호출하는 횟수,

f[n][1]은 n번째 피보나치 수열의 f(1)을 호출하는 횟수라고 하자

따라서, f[0][0] = 1, f[0][1] = 0 이다

그리고 n = 1일 때는 f[1][0] = 0, f[0][1] = 1이 된다

n = 2부터는 f(0)과 f(1)을 이용해 점화식으로 나타낼 수 있다

이는 아래와 같다

이미지 출처: 피보나치 수(위키백과)

위 그림의 식에 n = 2를 대입해 보면 f(2) = f(1) + f(0)이다

이는 f(1)을 1번 호출하고 f(0)을 1번 호출한다는 것을 뜻한다

f(3)은 어떻게 될까?

f(3) = f(2) + f(1)이다

f(2)는 f(1)를 1번, f(0)을 1번 호출한다고 했으니

f(3)은 f(1)를 2번, f(0)을 1번 호출한다

이를 일반화하여 아까 만든 2차원 배열로 나타내보자

f[n][0] = f[n-1][0] + f[n-2][0]
f[n][1] = f[n-1][1] + f[n-2][1]

가 된다

따라서 이를 코드로 나타내면 아래와 같다

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int fib[41][2];
// fib[n][0]: 0을 출력하는 개수, fib[n][1]: 1을 출력하는 개수

int main() {
    int T, n;
    int t, i;   // t: Test case의 횟수, i: fib[][]의 index
    fib[0][0] = 1;  // n = 0일 때 0을 출력하는 개수는 1
    fib[0][1] = 0;  // n = 0일 때 1을 출력하는 개수는 0
    fib[1][0] = 0;  // n = 1일 때 0을 출력하는 개수는 0
    fib[1][1] = 1;  // n = 1일 때 1을 출력하는 개수는 1

    scanf("%d", &T);
    for (t = 0; t < T; t++) {
        scanf("%d", &n);
        for (i = 2; i <= n; i++) {
            fib[i][0] = fib[i - 1][0] + fib[i - 2][0];
            fib[i][1] = fib[i - 1][1] + fib[i - 2][1];
        }
        printf("%d %d\n", fib[n][0], fib[n][1]);
    }
	return 0;
}