[JAVA] 백준 10870. 피보나치 수 5

이 글은 읽는데 약 4분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

풀이

n번째 피보나치 수를 구하는 문제이다.

피보나치 수는 0, 1, 1, 2, 3, 5, 8, 13, … 식으로 앞의 두 수를 더한 값이 현재 수가 되는 수열이다. 이것을 반복문과 재귀함수를 이용해서 풀어보자

반복문 이용

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

if(N < 2){
    sb.append(N);
}else{
    int a = 0;
    int b = 1;

    for(int i=2; i<=N; i++){
        int tmp = b;
        b = a + b;
        a = tmp;
    }

    sb.append(b);
}

일단 N이 0이면 결과는 0, 1이면 1이므로 N이 2 미만일 경우에는 N을 그대로 출력한다.
N이 2 이상일 경우를 보자.

먼저 0번 항을 변수 a로, 1번 항을 변수 b로 주고 각각 초기값을 0과 1로 지정한다.

위에서 사실상 1항 까지는 계산이 됐으므로 2항부터 계산하기 위해서 반복문의 i는 2부터 N을 포함하는 만큼 반복한다.

각 반복에 대해서 일단 b를 tmp변수에 저장해두고 b에는 a + b를, a에는 바뀌기 전의 b값을 저장한다.

이것을 반복하면 결국 b에 N번째 피보나치 수가 저장된다.

재귀함수 이용

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

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

    sb.append(fib(0, 1, N));

    System.out.println(sb.toString());
    br.close();
}

public static int fib(int a, int b, int n){
    if(n <= 1) return n;

    if(n == 2){
        return a + b;
    }else{
        return fib(b, a+b, n-1);
    }
}

이번에는 재귀함수로 풀어본다. 먼저 함수 fib를 호출하는데, 0번째 항과 1번째 항의 초기값인 0과 1을 넘겨주고, 재귀함수 실행 횟수를 제한하기 위해 N도 넘겨준다.

fib 함수 내부에서는 n이 1이하면 n을 그대로 반환한다. 이는 입력된 N이 0또는 1일때의 처리이다.

만약 N이 2라면 그냥 0과 1을 더한 1을 반환하게된다.

나머지의 경우에는 fib함수를 재귀적으로 호출하는데, 첫째 매개변수로는 b가 가고, 두번째로는 a + b가 간다. 또한 n-1을 하여 횟수를 하나 줄인다.

댓글