[BOJ/백준] 26529번 - Bunnies(Java 풀이/해답)

문제 바로가기: https://www.acmicpc.net/problem/26529

백준 solved.ac에 새로운 기능 마라톤이 생겼다
첫 번째 문제 Bunnies로, 브론즈2의 난이도, 재귀 연습으로 좋은 문제이다
핵심은 피보나치 구현이라, 영어 해석 관계없이 수식만으로 풀었다

 

문제

You’re going to raise farm animals and you decided to start with bunnies, the easiest of animals. To your surprise they are breeding like rabbits, so much so that you’re unable to count them accurately. However, you know that rabbits’ breeding patterns always follow the Fibonacci sequence. The Fibonacci sequence is defined as follows:

F(0) = 1, F(1) = 1, F(N) = F(N-1)+F(N-2)

Given the number of months the rabbits have been breeding, use the Fibonacci sequence to determine the number of rabbits you should have.

입력

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with a single integer x denoting the number of months that have passed since you bought your initial pair of rabbits. 0≤x≤45

 

출력

For each test case, output the expected number of rabbits after x months.

 

예제 입력

3
0
5
45

 

예제 출력

1
8
1836311903

 

조건

시간제한: 1초
메모리 제한: 1024MB

 

접근

단순한 피보나치 문제이다
효율을 위해 메모이제이션을 사용하며, 최대 주어지는 값이 45로, 1_836_311_903라 int 값으로도 충분해 보였다
재귀를 사용하였다

 

풀이

1. 테스트케이스 N을 입력받는다

2. N개의 수를 받으며 재귀를 수행한다

3. 사용 배열의 0,과 1번은 1로 초기화해준다

4. 빠른 출력을 위해 return 값을 스트링빌더에 append 해준다
   4-1. 배열의 x값이 0이 아니면(정보가 있다면) 해당 배열 값을 출력해준다
   4-2. 값이 없다면 재귀를 통해 이전 값들의 return 값으로 설정해준다

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 1. N 값 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 2. 피보나치 값 만들기
        // 45까지라서 21억을 넘지 않으므로 int형으로도 커버 가능하다
        int[] arr = new int[46];

        // 3. 피보나치 초기값 설정
        arr[0] = 1;
        arr[1] = 1;
        for(int i = 0; i < N; i++){

            // 4. 스트링 빌더에 계산 결과값 넣기
            sb.append(fibo(Integer.parseInt(br.readLine()), arr)).append("\n");
        }

        // 7. 출력
        System.out.println(sb);

    }

    public static int fibo(int n, int[] arr){
        // 5. 만약 해당 값이 있으면 바로 출력
        if(arr[n] != 0) return arr[n];

        // 6. 없으면 해당 값을 재귀로 계산
        return arr[n] = fibo(n - 1, arr) + fibo(n - 2, arr);
    }
}