[BOJ] 1003 피보나치 함수 - JAVA

1. 문제

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

1003번: 피보나치 함수

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);
    }
}

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

---

2. 풀이

2차원 배열

• Fn = Fn-1+Fn-2이므로 0의 수, 1의 수 역시 그렇게 구하면 된다. 
• 예를 들면 F3의 0 개수는 F2의 0 개수+F1의 0 개수이다.

import java.io.*;

public class BOJ_1003_피보나치함수 {
   static int[][] fib = new int[41][2];
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();

      fib[0][0] = 1;
      fib[1][1] = 1;

      while(--T>=0){
         int N = Integer.parseInt(in.readLine());
         fibonacci(N);
         sb.append(fib[N][0]).append(" ").append(fib[N][1]).append("\n");
      }
      System.out.print(sb);
   }

   private static void fibonacci(int n) {
      if(fib[n][0]!=0 || fib[n][1]!=0 || n<=1) return;

      fibonacci(n-1);
      fib[n][0] = fib[n-1][0]+fib[n-2][0];
      fib[n][1] = fib[n-1][1]+fib[n-2][1];
   }
}

 

1차원 배열

• 처음에 위의 코드대로 쉽게 2차원배열로 풀었다가 다른 규칙을 발견하고 다시 푼 코드다. 
• Fn의 0의 개수는 Fn-1, 1의 개수는 Fn임을 발견했다. 따라서 코드는 다음과 같다.
• 대신 N==0일때는 N-1 인덱스에 접근할 수 없으므로 따로 경우를 빼주었다.

import java.io.*;

public class BOJ_1003_피보나치함수 {
   static int[] fib = new int[41];
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();

      fib[0] = 0;
      fib[1] = 1;

      while(--T>=0){
         int N = Integer.parseInt(in.readLine());

         if(N==0) {
            sb.append("1 0\n");
            continue;
         }

         fibonacci(N);
         sb.append(fib[N-1]).append(" ").append(fib[N]).append("\n");
      }
      System.out.print(sb);
   }

   private static void fibonacci(int n) {
      if(n<2 || fib[n]!=0) return;

      fibonacci(n-1);
      fib[n] = fib[n-1]+fib[n-2];
   }
}

 

---

3. 결과

가장 아래에 있는 코드는 2차원 배열을 사용한 코드다. 중간의 틀린 코드는 무시하고 맨 위의 코드는 1차원 배열을 사용한 코드다.