피보나치 함수 - 1003

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.25 초 (추가 시간 없음)	128 MB	146939	41099	32063	30.981%

문제

다음 소스는 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이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1

3 0 1 3

예제 출력 1

1 0 0 1 1 2

예제 입력 2

2 6 22

예제 출력 2

5 8 10946 17711

 

Solution

https://github.com/anothel/BOJ/blob/main/app/1003_Fibonacci.cc

GitHub - anothel/BOJ

 

후기

피보나치수열은 코딩 테스트에서 비교적 간단한 알고리즘이다. 역시나 문제에서도 피보나치수열은 알려주고 0이 출력되는 1이 출력되는 개수를 출력하라고 한다. 그래서 간단하게 풀어봤다. 변수를 하나씩 지정하고 ++연산자로 해봤는데, 이게 ++연산이 엄청나게 많이 되는 것이다. 그래서 시간제한에 걸린다. 이 문제는 그렇게 간단하게 생각하라고 내놓은 문제가 아니고 동적 계획법이라는 아주 기가 막힌 컴퓨터공학 이론을 적용해서 풀어야 하는 문제였던 것이다. 사실 생각해보면 동적 계획법이라는게 별다른게 아니고 수열을 적어놓고 이게 어떠한 규칙에 의해서 이루어져있는지를 파악하는 것 정도가 될 것 같다.

 

Resources

- https://sihyungyou.github.io/baekjoon-1003/

- https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP