[알고리즘 / 백준] 2747 - 피보나치 수

 

문제는 위와 같으며 피보나치 수는 대표적인 재귀 문제이기 때문에 처음에 재귀 방식을 사용하였지만 시간 초과가 발생하여 단순히 for 문을 돌면서 문제를 해결하였습니다.

 

먼저 피보나치 수열을 사용한 파이썬 코드입니다.

from sys import stdin


def fibonacci(num):
    if num == 0:
        return 0

    if num == 1:
        return 1

    return fibonacci(num - 1) + fibonacci(num - 2)


n = int(stdin.readline())
print(fibonacci(n))

 

위 코드는 시간 초과 에러가 발생하기 때문에 for 문을 사용한 파이썬 코드를 보겠습니다.

from sys import stdin

n = int(stdin.readline())

a, b = 0, 1
while n > 0:
    a, b = b, a + b
    n -= 1

print(a)

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a = 0;
        int b = 1;

        int n = Integer.parseInt(br.readLine());

        while (n > 0) {
            int tmp = a + b;
            a = b;
            b = tmp;
            n -= 1;
        }

        System.out.println(a);
    }
}