백준 1003번 피보나치 함수

1. 문제

피보나치 함수

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1 복사

3
0
1
3

예제 출력 1 복사

1 0
0 1
1 2

예제 입력 2 복사

2
6
22

예제 출력 2 복사

5 8
10946 17711

 

 

2 - 1. 나의 풀이

숫자 0 1 2 는 구해놓고 3, 4, 5, 6 .... 부터 규칙을 구하려했다.

3부터 위로 올라가면서 역트리 형식으로 구해보니 0과 1의 출력횟수 또한 피보나치 함수라는 것을 대강 알았다.

 

정확한 수를 알기위해 직접 표를 그려서 구해보았다.

숫자	0	1	2	3	4	5	6	7	8
0 횟수	1	0	1	1	2	3	5	8	13
1 횟수	0	1	1	2	3	5	8	13	21

0과 1의 출력횟수에도 추가적인 규칙을 발견했다.

숫자 0을 제외하고,  숫자의 0 횟수는 직전 숫자의 1 횟수와 같다는 것.

즉 8의 0 횟수는 7의 1횟수와 같다는 것.

그래서 1 횟수만 표현한 배열을 만들었다.

(0 횟수 2차원 배열로 함께 만들어 두면 if(num==0) 조건을 반복하지 않아도 되어 더 빠르긴 하다)

 

//1 횟수 배열
int[] arr = new int[41];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < 41; i++) arr[i] = arr[i - 1] + arr[i -2];

위 처럼 1 횟수를 나타내는 배열을 저장한다.

 

for (int i = 0; i < t; i++) {
    int num = Integer.parseInt(br.readLine());
    if(num==0) sb.append(1 + " " + 0 + " \n");
    else sb.append(arr[num - 1]).append(" ").append(arr[num]).append(" \n");
}
//0 횟수 배열도 만들면 if(num == 0) 조건을 반복문마다 실행하지 않아도 되기에 더 빠르다.

위 코드를 합치면 끝이다.

 

2 - 2. 나의 코드

package solvedac;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ac1003_sol {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        int[] arr = new int[41];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i < 41; i++) arr[i] = arr[i - 1] + arr[i -2];

        for (int i = 0; i < t; i++) {
            int num = Integer.parseInt(br.readLine());
            if(num==0) sb.append(1 + " " + 0 + " \n");
            else sb.append(arr[num - 1]).append(" ").append(arr[num]).append(" \n");
        }
        System.out.println(sb);

    }
}

 

 

3. 얻어갈 점

1. 위 방법은 N이 40으로 배열로 미리 만들어놔도 지장이 없는 작은 수 이기에 가능한 풀이같다.

2. 0 횟수 배열도 미리 만들어 두면 약간 더 빠르다는 것.