[백준] 2502 떡 먹는 호랑이

옛날에 생각 못하고 넘어갔는데 다시보니 너무 쉽다..!

 

처음을 A, 다음을 B라고 생각하고 몇번 써보면 피보나치가 완성이 된다

그리고 알 수 있는 규칙은 B = fib[A+1]이라는 사실이다

 

이걸 이용해서 식을 풀어보자

수학으로 풀 수 있다!

 

aA +  bB = K 인것을 이용해보자

 

소스코드

#include <iostream>
using namespace std;
int A[33];
int B[33];
int D, K;
 
int main() {
    A[1] = 1;
    B[2] = 1;
    for (int i = 3; i <= 30; i++) {
        A[i] = A[i - 1] + A[i - 2];
        B[i] = B[i - 1] + B[i - 2];
    }
    scanf(" %d %d", &D, &K);
 
    int a = A[D], b = B[D];
    for (int i = 1; i <= 1000000; i++) {
        if ((K - a * i) % b == 0) {
            printf("%d\n", i);
            printf("%d\n", (K - a * i) / b);
            return 0;
        }
    }
}