[백준 1003번] 피보나치 수열

1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

피보나치수열 계산을 Buttom-Down 형식인 재귀로 풀어나갈 때 fibonacci(0), fibonacci(1)이 각각 몇 번 호출되는지 구하는 문제이다.

input data로 테스트케이스의 갯수와 구하고자 하는 피보나치 값이 주어진다.

input data의 피보나치 값은 0<= N <=40인 정수이고, 

output data로 각 테스트 케이스별로 한 줄에 fibonacci(0) fibonacci(1)의 값을 출력해준다.

시간제한은 0.25초이다.

 

2. 나의 방식대로 문제를 재정의 하자.

이를 재귀함수 형태로 구현하고, 이때 사용되는 0, 1에 대해 Memorization을 한다.

fiboZero[n] = n번째 피보나치수열에서 사용된 0 등장 횟수

fiboOne[n] = n번째 피보나치수열에서 사용된 1 등장 횟수

피보나치수열의 값을 구하는 과정과 동일하게 문제의 값을 구한다.

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

재귀 함수 (Top-down)이나 반복문(Bottom-UP)을 사용한다.

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader를 통해서 입력

 

2) 시간 복잡도 계산

n까지 계산하므로 O(n)

 

5. 주의할 점은 무엇인가?

제한시간이 0.25초인 점

 

6. 풀이 과정

fiboZero[n] = n번째 피보나치 수열에서 사용된 0 등장 횟수

fiboZero[n] = fiboZero[n-1] + fiboZero[n-2] 

fiboZero[0] = 1

fiboZero[1] = 0

 

fiboOne[n] = n번째 피보나치 수열에서 사용된 1 등장 횟수

fiboOne[n] = fiboOne[n-1] + fiboOne[n-2] 

fiboOne[0] = 0

fiboOne[1] = 1

 

Buttom-UP 방식

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] fiboZero = new int[41];
        int[] fiboOne = new int[41];
        fiboZero[0] = 1;
        fiboZero[1] = 0;
        fiboOne[0] = 0;
        fiboOne[1] = 1;

        Integer T = Integer.parseInt(br.readLine()); // testcase
        Integer n = 0;

        for (int i = 0; i < T; i++) {
            n = Integer.parseInt(br.readLine());
            for (int j = 2; j <= n; j++) {
                fiboZero[j] = fiboZero[j - 1] + fiboZero[j - 2];
                fiboOne[j] = fiboOne[j - 1] + fiboOne[j - 2];
            }
            
            bw.write(fiboZero[n]+" "+ fiboOne[n] + "\n");

        }

        bw.flush();
        br.close();
        bw.close();
    }
}

메모리: 16012KB

시간: 156ms

 

Top-down 방식

import java.io.*;

public class Main {
    static int[] fiboZero = new int[41];
    static int[] fiboOne = new int[41];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        fiboZero[0] = 1;
        fiboZero[1] = 0;
        fiboOne[0] = 0;
        fiboOne[1] = 1;

        Integer T = Integer.parseInt(br.readLine()); // testcase
        Integer n = 0;

        for (int i = 0; i < T; i++) {
            n = Integer.parseInt(br.readLine());
            
            bw.write(fiboZ(n) + " " + fiboO(n) + "\n");

        }

        bw.flush();
        br.close();
        bw.close();
    }
    
    static int fiboZ(int n) {
        if (n == 0 || n == 1) {
            return fiboZero[n];
        }

        if (fiboZero[n] != 0) {
            return fiboZero[n];
        }
        fiboZero[n] = fiboZ(n - 1) + fiboZ(n - 2);

        return fiboZero[n];
    }
    
    static int fiboO(int n) {
        if (n == 0 || n == 1) {
            return fiboOne[n];
        }

        if (fiboOne[n] != 0) {
            return fiboOne[n];
        }
        fiboOne[n] = fiboO(n - 1) + fiboO(n - 2);

        return fiboOne[n];
    }
}

메모리: 15940KB

시간: 152ms

 

7. 다른 풀이와 비교했을 때 개선점

int형 리스트를 작성할 때 memory [41][2] 형식을 사용했으면 조금 더 깔끔한 코드가 되었을 것이다.