[백준] 1003번 : 피보나치 함수 – JAVA [자바]

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

1003번: 피보나치 함수

 

---

• 문제

 

 

---

• 문제 풀이

백준 1003번 피보나치 함수는 실버 3 난이도의 DP 문제이다. 이 문제에서는 피보나치의 소스 코드가 C++ 언어로 작성되어 있다. 이 소스 코드는 밑에서 볼 수 있다.

 

//피보나치 소스 코드
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);
    }
}

 

이 소스 코드에서는 n = 0이면 0을 출력하고 n = 1이면 1을 출력하고 그 외에는 fibonacci (n - 1) + fibonacci (n - 2)를 출력한다. 이때 N이 주어졌을 때 0과 1이 몇 번 출력되는지를 출력하면 된다.

 

이 문제는 예시를 보면 쉽게 패턴을 찾을 수 있다. n = 0부터 n = 8까지의 예시를 보겠다.

 

n = 0

n = 0이면 0만 바로 출력하므로 "1  0"이 출력된다.

 

n = 1

n = 1이면 1만 바로 출력하기 때문에 "0  1"이 출력된다.

 

n = 2

n = 2이면 fibonacci(1) + fibonacci(0)을 호출하기 때문에 0과 1이 각각 1번씩 출력된다. 따라서 "1  1"이 출력된다.

 

n = 3

n = 3이면 fibonacci(1) + fibonacci(2)를 호출한다. 근데 이전에 fibonacci(2)는 "1 1"을, fibonacci(1)은 "0 1"을 출력하기 때문에 "1  2"를 출력한다.

 

n = 4

n = 4이면 fibonacci(3) + fibonacci(2)를 호출한다. 이전에 fibonacci(3)은 "1 2"를, fibonacci(2)는 "1 1"을 출력했기 때문에 n = 4일 때 "2  3"을 출력한다.

 

이 패턴을 토대로 표로 표시하면 다음과 같다.

 

n	0	1	2	3	4	5	6	7	8
출력	1  0	0  1	1  1	1  2	2  3	3  5	5  8	8  13	13  21

 

이 표에서 볼 수 있듯이 0과 1을 출력하는 것도 피보나치 패턴을 따른다. 

 

따라서 이 문제를 풀 때 long형 또는 int형 배열 DP를 선언한다. 그리고 dp [1] = 1로 초기화해주고 나머지는 for-loop을 이용해서 채워준다. 그리고 N이 주어졌을 때 0을 출력하는 횟수는 dp [N - 2]이고 1을 출력하는 횟수는 dp [N - 1]이 된다.

 

자세한 코드는 밑에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        long[] dp = new long[41];  //DP 배열 초기화
        StringBuilder sb = new StringBuilder();
        dp[1] = 1;
        for (int i = 2; i <= 40; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            //0이면 1 0 출력
            if (n == 0) {  
                sb.append("1 0\n");
                continue;
            }
            sb.append(dp[n-1] + " " + dp[n] + "\n");
        }
        System.out.print(sb);
    }
}