[BOJ] 1003번: 피보나치 함수

1003번: 피보나치 함수

풀이

그래프를 그려보면 0과 1이 호출될 때 일정한 규칙이 나오는 것을 알 수 있다.
그래서 dp[i][0]은 i번째 수에서 0의 호출 횟수이고 dp[i][1]은 i번째 수에서 1의 호출 횟수이다.

또는 N이 주어질 때 dp[N]은 0의 호출 횟수이고 dp[N+1]은 1의 호출 횟수가 되는데 이 이유는 잘 모르겠다... (아시는 분은 알려주시면 정말 감사드리겠습니다!)

코드

1번째

#include <stdio.h>
int main()
{
    int n, k;
    scanf("%d", &n);
    for (int j = 0; j < n; ++j) {
        scanf("%d", &k);
        int dp[42] = { 1, 0 };
        for (int i = 2; i <= 41; ++i) dp[i] = dp[i - 1] + dp[i - 2];
        printf("%d %d\n", dp[k], dp[k + 1]);
    }
    return 0;
}

2번째

#include <stdio.h>
int main()
{
    int n, k;
    scanf("%d", &n);
    for (int j = 0; j < n; ++j) {
        scanf("%d", &k);
        int dp[40][2];
        dp[0][0] = 1, dp[0][1] = 0;
        dp[1][0] = 0, dp[1][1] = 1;
        for (int i = 2; i <= k; ++i) {
            dp[i][0] = dp[i - 2][0] + dp[i - 1][0];
            dp[i][1] = dp[i - 2][1] + dp[i - 1][1];
        }
        printf("%d %d\n", dp[k][0], dp[k][1]);
    }
    return 0;
}