1003번 피보나치 함수 - DP

#include <stdio.h>

typedef struct _values  //두 개의 숫자를 반환하기 위한 구조체
{
    int one;
    int zero;
} values;

int note[41][2];  //메모리제이션

values fibonacci(int N) {
    values a, b, c;
    a.one=a.zero=b.one=b.zero=c.one=c.zero=0;  //구조체 초기화
    
    if(note[N][0] || note[N][1]) {  //메모되있을 경우 사용
        a.one+=note[N][1];
        a.zero+=note[N][0];
        
        return a;
    }
    
    c = fibonacci(N-2);  //재귀함수
    b = fibonacci(N-1);

    a.zero = b.zero + c.zero;
    a.one = b.one + c.one;
    note[N][0] = a.zero;
    note[N][1] = a.one;
    
    return a;
}

int main()
{
    int T, N; // 테스트 케이스의 개수 T, 숫자 N
    values result;
    int i, j, k;
    
    note[1][1]=1; note[0][0]=1;
    
    scanf("%d", &T);
    
    for(i=0; i<T; i++) {  //테스트 케이스 수만큼 반복
        scanf("%d", &N);
        
        result = fibonacci(N);
        printf("%d %d\n", result.zero, result.one);
    }
    
    return 0;
}

 

기존 피보나치 수열과 달리 함수에서 두 개의 값을 반환해야 한다. 포인터를 이용하는 방법, 구조체를 이용하는 방법, 16바이트에 두 개의 수를 끼워 넣는 방법 등등이 있었고 나는 구조체를 반환하는 방법을 해결하였다. 메모리제이션 기법을 사용하였다.

 

구조체 초기화를 안해서 15분 정도 헛짓거리를 했었던 것 같다. 변수가 아닌 구조체도 초기해야 한다는 것을 명심하자.

 

두 개의 수를 반환하는 방법은 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=1004kiwoo&logNo=60102081613 

함수 return 방법(2개이상의 값을 반환시)

이 블로그에 자세히 나와있어서 여기서 공부했다.