[BOJ] 2502 - 떡 먹는 호랑이 (C++)

문제

떡 먹는 호랑이

코드

#include <iostream>

using namespace std;

int D, K;
int a[31], b[31];

int main(void){
    cin >> D >> K;

    a[1] = 1; a[2] = 0;
    b[1] = 0; b[2] = 1;
    for (int i = 3; i <= D; i++){
        a[i] = a[i-1] + a[i-2];
        b[i] = b[i-1] + b[i-2];
    }

    for (int i = K/b[D]; i > 0; i--){
        if ((K-i*b[D])%a[D] == 0) {
            cout << (K-i*b[D])/a[D] << endl;
            cout << i << endl;
            break;
        }
    }
    return 0;
}

접근

첫째날의 떡 개수를 a, 둘째날의 떡 개수를 b라고 생각하였다. 이를 바탕으로 각 날짜 별로 주게 되는 떡의 개수를 계산한다면 m*a + n*b개가 된다. 따라서 우리가 D일차 떡의 개수를 통해 a, b에 들어갈 수 있는 값을 알기 위해서는 각각의 계수 m, n을 알아야 한다. 이는 피보나치 수열의 특징을 가지고 있기 때문에 쉽게 계산해서 알아낼 수 있다. 각 계수를 구한 이후에는 D일차 떡의 개수 K개를 이용하여 조건을 만족하는 a, b 값을 찾아주면 된다.