[BOJ] 백준 2502 떡 먹는 호랑이

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

 Input 
6 41　 

 Output 

2

7

만족하는 A, B 조합이 1개 이상일 수 있는 Special judge 유형 문제입니다.

 

첫번째 날 떡의 개수 = A, 두번째 날 떡의 개수 = B 라고 했을 때,

▶ A → B → A + B → A + 2B → 2A + 3B → 3A + 5B → 5A + 8B → 8A + 13B

[B의 관점]: 2번째 항부터 계수의 변화가 1 → 1 → 2 → 3 → 5 → 8 → 13 → ... 로서, 피보나치 수열을 형성합니다.

B의 계수가 fibo(n)일 때, A의 계수는 fibo(n-1)에 해당합니다.

 

문제에서 주어지는 D를 고려하면 B의 계수는 fibo(D-1)이며, A의 계수는 fibo(D-2) 입니다.

ex) D = 6 → fibo(4) = 3, fibo(5) = 5 → 3A + 5B = 41(=K)이기 때문에

      → A = 2, B = 7인 경우 → 3 * 2 + 7 * 5 = 41로 만족합니다.

▶ 피보나치 수열로 A와 B의 계수를 구한 후, A와 B의 숫자에 완전 탐색처리

---

#include <stdio.h>
 
int fibo(int n) {
    int ret = 1;
    if (n == 1 || n == 2)
        return ret;
 
    int x=1, y=1;
    for (int i = 3; i <= n; ++i) {
        ret = x + y;
        x = y, y = ret;
    }
    return ret;
}
 
int main() {
    int D, K, A = 1, B, sum;
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &D, &K);
 
    int x = fibo(D - 2), y = fibo(D - 1);
    while (1) {
        sum = 0;
        sum += x * A;
        B = 1;
        while (1) {
            sum += y * B;
            if (sum > K) break;
 
            if (sum == K) {
                printf("%d\n", A);
                printf("%d\n", B);
                return 0;
            }
            sum -= y * B;
            B++;
        }
        A++;
    }
}