[C/C++] 백준 #2502 떡 먹는 호랑이(구현)

이번 문제는 알고리즘이 무엇이라고 이야기하기가 어렵습니다.  그냥 구현이라고 하도록 하겠습니다.

 

떡 먹는 호랑이

 

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

 

피보나치 수열은 동적 계획법(dynamic programming)이나 재귀함수(recursion)이 나올 때 자주 등장하는 문제입니다.  일반적으로는 첫번째 항이 1, 두번째 항이 1인 경우입니다.  이번 문제는 d번째 항의 값이 주어졌을 때, 가능한 첫번째 항과 두번째 항 중 하나를 출력하면 됩니다.

 

피보나치 수열의 첫번째 항을 A 두번째 항을 B라고 한다면, 세번째 항은 A+B로 표현할 수 있습니다.  이것을 쉽게 AB라고 표현할께요.  세번째 항이 7이었다면, A+B = 7 이 되는 수를 구하면 됩니다.  B가 A보다 크거나 같다는 조건이 있으니, (1, 6), (2, 5), (3, 4) 세가지 경우가 있겠죠.  이 중 아무것이나 출력하면 됩니다.  자 이렇게 나가면 4번째 항은 ABB가 됩니다.  5번째 항은 AABBB 가 되겠죠.  4번째 항은 AAABBBBB이 됩니다.  자 이 A항을 거슬러 올라가면, 1 0 1 1 2 3 ... 형태가 될겁니다.  B 항도 보면 0 1 1 2 3 5 ... 형태가 되겠죠.  사실 A와 B의 갯수도 결국 피보나치 수열을 이루게 됩니다.  k번째 피보나치 수열을 \(f_{k}\)라고 한다면,

\[ f_{k} = f_{k-2}A + f_{k-1}B \]

로 표현이 됩니다.  그 다음에는 부정방정식이기 때문에 A 값을 증가시켜가며 B의 값을 찾으면 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2502
//        - by Aubrey Choi
//        - created at 2019-07-12
//------------------------------------------------
#include <stdio.h>

int fib(int n)
{
    int f[2] = {0, 1};
    for(int i = 1; i <= n / 2; i++)
    {
        f[0] += f[1];
        f[1] += f[0];
    }
    return f[n & 1];
}

int main()
{
    int d, k;
    scanf("%d%d", &d, &k);
    int x = fib(d), y = fib(d - 1);
    for(int a = 1; a <= k/x; a++)
    {
        if((k - a * x) % y == 0)
        {
            int b = (k - a * x) / y + a;
            printf("%d\n%d\n", a, b);
            break;
        }
    }
    return 0;
}