[Algorithm]Baekjoon 2502번 :: 떡 먹는 호랑이

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

2502번: 떡 먹는 호랑이

 
 
using namespace std;
 
int d, k;
pair<int, int> coefficients[31];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> d >> k;
 
    coefficients[1] = { 1,0 };
    coefficients[2] = { 0,1 };
 
    for (int i = 3; i <= d; ++i)
    {
        coefficients[i] = { coefficients[i - 1].first + coefficients[i - 2].first, coefficients[i - 1].second + coefficients[i - 2].second };
    }
 
    int targetCoefficientA = coefficients[d].first;
    int targetCoefficientB = coefficients[d].second;
    int curA = 1;
 
    while (1)
    {
        int result = k - targetCoefficientA * curA;
        if (result % targetCoefficientB == 0)
        {
            cout << curA << endl << result / targetCoefficientB;
            break;
        }
 
        ++curA;
    }
}
 
 
 
 

 

d번째 되는날 k개의 떡개수로 첫째날과 둘째날에 받은 떡의 개수를 구하는 문제이다.

 

첫째날 받은 떡의 개수를 A개, 둘째날 받은 떡의 개수를 B개라 했을 때, 셋째날 받은 떡의 개수는 A+B개이다.

피보나치처럼 값이 업데이트되는데, 이렇게 업데이트하다 보면 d번째 받은날의 xA + yB를 알 수 있다.

즉, A, B의 계수를 알 수 있다. 예시로 말하자면, 값을 업데이트하다보면 6번째날은 3A + 5B개이다.

 

이 때 받은 떡의 개수가 41개라 했으니, 3A + 5B == 41이다.

그러면 이제 41을 만족하는 A와 B를 구해야한다. 만족하는 쌍의값은 여러개가 나올수 있다.

그리고 B는 항상 A보다 크거나같아야한다.  

그렇기때문에 A에다가 먼저 1을 넣고 하나씩 늘려가서 비교하면 된다.

A에다가 1을 넣는다가정하면 3 + 5B == 41을 만족해야한다. 하지만 41-3인 38은 절대 5B가 될 수 없다.

B는 자연수여야만 하는데, 38은 5의배수가 아니기 때문에 해당값을 만족하는 자연수는 존재하지 않는다.

그러니 해당차례는 넘어가고 다시 A값을 증가시켜서 A에다가 2를 넣어본다.

그러면 41-6 == 35 == 5의 배수  가 되기 때문에 올바른 정답이 나온다.