[ 백준 / C ] 1003번 : 피보나치 함수

1003

#include <stdio.h>
#include <stdlib.h>

// // 배열 버전
// void fibonacci_count(int n, int*count_0, int*count_1){
//     int count_arr [2][2]= {{1,0},{0,1}};
    
//     if(n == 1){
//         *count_0 = count_arr[1][0];
//         *count_1 = count_arr[1][1];
//     }
//     for(int i = 2; i <= n; i++){
//         *count_0 = count_arr[0][0] + count_arr[1][0];
//         *count_1 = count_arr[0][1] + count_arr[1][1];

//         count_arr[0][0] = count_arr[1][0];
//         count_arr[0][1] = count_arr[1][1]; 
//         count_arr[1][0] = *count_0;
//         count_arr[1][1] = *count_1; 
//     }
// }

// 동적 프로그래밍 피보나치 수 함수로 0과 1 카운트
void fibonacci_count(int n, int*count_0, int*count_1){
    int ppre_count_0 = 1;
    int ppre_count_1 = 0;
    int pre_count_0 = 0;
    int pre_count_1 = 1;
    
    if(n == 1){
        *count_0 = pre_count_0;
        *count_1 = pre_count_1;
    }
    for(int i = 2; i <= n; i++){
        *count_0 = pre_count_0 + ppre_count_0;
        *count_1 = pre_count_1 + ppre_count_1;

        ppre_count_0 = pre_count_0;
        ppre_count_1 = pre_count_1; 
        pre_count_0 = *count_0;
        pre_count_1 = *count_1; 
    }
}



int main(void){
    // 테스트 케이스 입력
    int test_case = 0;
    scanf("%d", &test_case);

    for(int i = 0; i < test_case; i++){
        // 숫자 입력
        int num = 0;
        scanf("%d", &num);

        // 피보나치 0과 1 카운트
        int count_0 = 1;
        int count_1 = 0;
        fibonacci_count(num, &count_0, &count_1);

        // 출력 
        printf("%d %d\n", count_0, count_1);
    }
    return 0;
}

이번꺼는 문제에 있는 함수 그대로 사용하면 재귀함수 사용해서 하는거라 시간초과가 나서 동적프로그래밍 방법으로 해야했었다.

근데, 하면서 피보나치로 값을 출력해야하는게 아니라 그냥 0과 1이 몇 번 카운트 되어야 하는지만 중요한 문제같다는 생각을 해서,,

값출력은 지우고 0과 1 카운트에만 집중해서 패턴 찾으니까 있어서 처음에는 배열로 시도했었다.

// 동적 프로그래밍 피보나치 수 함수
void fibonacci(int n, int*count_0, int*count_1){
    int *c0=malloc(sizeof(int)*n);
    int *c1=malloc(sizeof(int)*n);
    c0[0]=1;
    c0[1]=0;
    c1[0]=0;
    c1[1]=1;

    for(int i = 2; i <= n; i++){
        c0[i] = c0[i-1] + c0[i-2];
        c1[i] = c1[i-1] + c1[i-2];
    }
    *count_0 = c0[n];
    *count_1 = c1[n];
    
    free(c0);
    free(c1);
}

int main(void){
    int test_case = 0;
    scanf("%d", &test_case);

    for(int i = 0; i < test_case; i++){
        int num = 0;
        scanf("%d", &num);

        int count_0 = 0;
        int count_1 = 0;
        fibonacci(num, &count_0, &count_1);

        printf("%d %d\n", count_0, count_1);
    }
    return 0;
}

근데 위와 같이 메모리 초과가 떠서 ㅎㅎ,,, 아 안되겠다 싶어서

우리가 원하는 값을 얻으려면 전값, 전전값만 기억하고 있으면 되니까 맨 위의 코드로 바꿔서 시도했더니 ^ㅁ^ 성공 ~

밑에는 패턴이에유 

 

---

0 1 0
1 0 1
2 1 1
3 1 2
4 2 3

0
pp = 1 0
1
p = 0 1
2
c = 1 1,  pp = 0 1, p = 1 1
3
c = 1 2,  pp = 1 1, p = 1 2
4
c = 2 3,  pp = 1 2, p = 2 3