[백준] 10870번 : 피보나치 수 5 (브론즈 Ⅱ) - Java/자바

---

✅ 문제

문제링크

🔗 https://www.acmicpc.net/problem/10870

 

---

✅ 풀이

🔹 코드 1 (재귀 호출)

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));
        int n = Integer.parseInt(br.readLine());
        System.out.println(fibonacci(n));
    }

    public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

 

이 문제는 피보나치의 수열에 관한 문제이다.

피보나치의 수열은 다음 식으로 표현할 수 있다.

$F_{\;n}\;=\;F_{\;n\;-\;1}\;+\;F_{\;n\;-\;2}\;(n\;\leq\;2)$

재귀 호출을 사용해 해결해보자.

 

n을 입력받고 0번째부터 시작해서 n번째 피보나치의 수를 출력해야한다.

fibonacci(n)의 반환값을 출력해주도록 한다.

 

fibonacci (int n) 메서드

n번째 피보나치의 수를 구해 int로 반환하는 메서드이다.

if문에 조건을 n == 0일 때는 return 0;하고 if문에 조건을 n == 1일 때는 return 1;을 한다.

아닌 경우에는 return fibonacci(n - 1) + fibonacci(n - 2);하여 재귀 호출을 하도록 한다.

 

🔹 결과 1

 

🔹 코드 2 (반복문)

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));
        int n = Integer.parseInt(br.readLine());

        int fibonacci = 1;
        if (n == 0) {
            fibonacci = 0;
        }
        int prev = 0;
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            temp = fibonacci;
            fibonacci += prev;
            prev = temp;
        }
        System.out.println(fibonacci);
    }
}

 

피보나치 수열을 반복문을 사용해 해결해보자.

 

n을 입력받고 int fibonacci = 1;로 선언한다.

if문에 조건을 n == 0하여 n이 0일때는 fibonacci = 0;하도록 한다.

int prev = 0;하여 이전 값을 저장할 변수를 선언하고 int temp = 0;하여 temp에는 이전의 피보나치의 수를 저장할 용도로 선언한다.

 

for문을 i = 2부터 n보다 작거나 같을 동안 반복하고 temp = fibonacci;하여 temp에 우선 이전 fibonacci의 값을 저장한다.

fibonacci += prev;하여 이전 값을 더해 피보나치의 수를 구하고 prev = temp;하여 이전 피보나치의 수를 저장한다.

즉, 여기서 n번째 피보나치의 수를 구할 때 더하기 전의 fibonacci는 n - 1번째, prev는 n - 2번째 피보나치의 수 역할을 한다.

 

반복이 모두 종료되면 fibonacci를 출력해주도록 한다.

 

🔹 결과 2

 

🔹 코드 3 (int 배열, 반복문)

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));
        int n = Integer.parseInt(br.readLine());
        int[] fibonacci = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            if(i == 0) fibonacci[0] = 0;
            else if(i == 1) fibonacci[1] = 1;
            else fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        System.out.println(fibonacci[n]);
    }
}

 

int 배열을 사용해 해결해보도록 하자.

 

n을 입력받고 0번째부터 시작하므로 배열 크기를 n + 1로 생성하도록 한다.

int[] fibonacci = new int[n + 1];하여 int 배열을 생성한다.

 

for문을 i = 0부터 n보다 작거나 같을 동안 반복한다.

if문에 조건을 i == 0하여 i가 0일 때는 fibonacci[0] = 0;하여 저장한다.

else if문에 조건을 i == 1하여 i가 1일 때는 fibonacci[1] = 1;하여 저장한다.

이외의 경우에는 fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];하여 계산해주도록 한다.

 

반복이 종료되면 fibonacci[n]을 출력해주도록 한다.

 

🔹 결과 3

 

🔹알게된 정보

• 피보나치의 수를 구하는 방법을 재귀 호출과 반복문, int 배열을 사용한 반복문을 통해 구현해보았다.

 

---