1003 - 피보나치 함수

(문제보기)

 

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

피보나치 함수 성공분류

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.25 초 (추가 시간 없음)

128 MB

107055

27209

21437

29.839%

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1 2 3 4 5 6 7 8 9 10 11

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

 

0. 동적계획법의 이해

 

동적계획법이란 재귀함수를 여러번 호출하다보면 이전에 호출된 함수를 다시 호출하는 경우가 생긴다.

이를 좀더 효율적으로 계산하기 위한 방법이라고 생각하면 된다.

 

말로만 설명하면 이해하기 힘들기때문에 문제를 살펴보자. 바로 이해가 될 것이다.

 

1. 문제 분석

 

피보나치 수를 구하는 문제이다. 다만 기존의 방식에는 개선점이 있다.

 

 

위의 경우 fib(5)를 계산하는 과정이다.

재귀적으로 계속 계산하여 깊어지는데, 빨간색 동그라미를 친 부분을 살펴보자.

fib(2)를 구하는 과정인데, 맨 왼쪽에서 2를 구했음에도 불구하고 2번이나 fib(2)를 더 수행하였다.

 

따라서 이러한 불필요한 계산을 줄이고자 먼저 계산한 fib(2)를 저장하고 다음번에 사용할 때는 계산을 하지 않고 저장된 fib(2)의 값을 불러오자는 것이 동적 계획법의 아이디어다.

 

이 문제에서는 fib(N)을 계산할 때 0과 1을 몇번을 계산하는지를 묻는 문제이다.

처음에는 0과 1을 카운팅할 배열을 2개를 선언하였으나 시간초과로 인하여 풀지 못했다.

 

그러다 배열 하나로 풀 수 있도록 만들어주는 한가지 규칙이 있었는데,

 

각 배열은 앞의 두 수를 더한 값이 된다.

또한 각 배열을 묶어보면 0의 갯수와 1의 갯수로 나타난다.

 

4의 경우 0이 2, 1이 3개 나타난 모습이다.

 

이를 활용하여 문제를 해결했다.

 

 

2. 소스코드

// #1003

#include<stdio.h>

int array[42] = {1, 0, 1};

int fib(int num){
        if(array[num] != -1) return array[num];
        else if(num == 0)
                return 0;
        else if(num == 1)
                return 1;
        else{
                array[num] = fib(num-1) + fib(num-2);
                return array[num];
        }
}
int main(void){
        /* init array */
        for(int i=3; i<42; i++)
                array[i] = -1;

        int N, T;

        scanf("%d", &T);
        for(int i=0; i<T; i++){
                scanf("%d", &N);
                fib(N+1);
                printf("%d %d\n", array[N], array[N+1]);
        }
        return 0;
}

 

맨처음에는 배열 2개를 활용하여서 0과 1을 카운팅 하니까 시간초과로 문제를 풀지 못했는데 저러한 규칙을 이용하여서 푸니까 금방 풀렸다.

 

저런생각은 어떻게 하는지 대단하다..