[JAVA / 자바] 백준 1003번 - 피보나치 함수

문제

다음 소스는 N번째 피보나치 수를 구하는 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);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

---

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

 

---

문제 접근 방법

피 보나 치수를 구하는 함수를 문제에서 주어준 대로 작성하게 되면 시간 초과가 나게 된다.

피노 나치수는 구하려는 수가 n번째 수라고 할 때, n-1번째 수와 n-2번째 수를 있어 붙인 수이다.

따라서 다이나믹 프로그래밍(Dynamic Programming)으로 최초 1회만 구해놓고 배열에 저장해 두었다가 이후 입력되는 수가 구했던 수보다 작은 수라면 배열에서 단순히 호출하여 출력해주면 되고, 그렇지 않고 큰 수가 들어온다면 마지막으로 구했던 수에 이어서 원하는 수까지 마저 구해주면 된다.

그냥 피보나치 수를 구하는 문제면 위와 같이 해주면 되겠지만, n번째의 피 보나 치수에서 1과 0의 개수를 각각 출력하라 했으므로, 크게 어려울 것 없이 1과 0을 각각 카운트하여 위 방법과 동일하게 해결해주면 된다.

---

JAVA 코드 풀이

코드 실행 결과

---

후기

피보나치 수열을 이전에는 재귀 방법 외에 다이나믹 프로그래밍 같이 사용하여 구할 수 있다는 생각을 하지 못했다. 이번 문제를 풀면서 다이나믹 프로그래밍에 익숙해지면 연산 횟수가 줄어들어 훨씬 시간적인 측면에서 절약이 많이 될 것 같다. (살짝 메모리로 시간을 사는 느낌,,?) 반복된, 불필요한 연산을 줄이는 게 어떻게 보면 효율적인 측면에서 중요하다 생각하는데 다이나믹 프로그래밍이 그러한 면에서는 좋은 알고리즘이라고 생각한다.

---

문제 원본

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

1003번: 피보나치 함수