[ 백준 2502 ] 떡 먹는 호랑이 (C++)

백준의 떡 먹는 호랑이(2502) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

첫 째날과 둘 째날에 호랑이에게 준 떡의 갯수를 구해야 하는 문제이다. 과정에 따라서 순차적으로 정답을 도출해내보자.

#1. 첫 째날과 둘 째날 호랑이에게 준 떡의 갯수

그럼 가장 먼저 첫 째날과 둘 째날 호랑이에게 준 떡의 갯수에 따라서 떡의 갯수가 어떻게 변하는지 알아보자.

간단하게 첫 째날 호랑이에게 준 떡의 갯수를 'A개', 둘 째날 호랑이에게 준 떡의 갯수를 'B개' 라고 생각해보자.

그리고 이 갯수들을 토대로 몇 일까지만 떡의 갯수를 계산해보자.

첫 째날 호랑이에게 준 떡의 갯수 = A 개

둘 째날 호랑이에게 준 떡의 갯수 = B 개

셋 째날 호랑이에게 준 떡의 갯수 = A + B 개

넷 째날 호랑이에게 준 떡의 갯수 = A + 2B 개

다섯 째날 호랑이에게 준 떡의 갯수 = 2A + 3B 개

여섯 째날 호랑이에게 준 떡의 갯수 = 3A + 5B 개

일곱 째날 호랑이에게 준 떡의 갯수 = 5A + 8B 개

뭐 이런식으로 계산이 될 것이다. 우리는 위의 예시들을 통해서 다음과 같은 정보를 얻을 수 있다.

첫 째날과 둘 째날의 떡의 갯수만 알 수 있다면, 그 외의 나머지 날들의 떡의 갯수는 A와 B를 이용한 식으로 나타낼 수 있다.

즉, A와 B에 적당한 계수가 붙음으로써 비율의 개념으로 계산을 할 수가 있다 라는 것을 알 수 있다.

그래서 본인은 지금부터 이 '비율'을 구할 것이다.

이를 위해서 지금부터 2가지 수식을 한번 사용해보자.

A[a] = b 라는 수식과, B[a] = b 라는 수식을 사용할 것이다.

A[a] = b의 의미는 "a번째날 호랑이에게 준 떡의 갯수를 구할 때 'A'앞에 붙는 계수는 b입니다." 를 의미하고

B[a] = b의 의미는 "a번째날 호랑이에게 준 떡의 갯수를 구할 떄 'B'앞에 붙는 계수는 b입니다." 를 의미한다.

이 수식의 초기값을 채워보면 다음과 같을 것이다.

A[1] = 1 , B[1] = 0.

A[2] = 0 , B[2] = 1.

다시한번 이 수식을 설명해보자면, 첫 째날은 'A개'를 호랑이에게 줄 것이다. 이를 'A'와 'B'를 이용해서 보다 더 정확하게 수식을 적어보자면 다음과 같다.

첫 째날 호랑이에게 준 떡의 갯수 = 1A + 0B

둘 째날 호랑이에게 준 떡의 갯수 = 0A + 1B

따라서, A[1]의 값, 즉, 첫 째날 호랑이에게 준 떡의 갯수를 구할 때 'A'앞에 붙는 계수는 '1'이라는 결과를 얻을 수 있다.

반대로, 첫 쨰날 호랑이에게 준 떡의 갯수를 구할 때 'B'앞에 붙는 계수는 '0'이므로 B[1] = 0이라는 결과를 얻게 된다.

둘 째날도 마찬가지이다. A[2]의 값은 둘 째날 호랑이에게 준 떡의 갯수를 구할 때 'A'앞에 붙는 계수는 '0'이므로

A[2] = 0 이라는 결과를 얻을 수 있고, B[2] = 1이라는 결과를 얻게 된다.

그럼 이를 초기식으로 셋째날부터는 어떻게 구하게 될까 ??

문제에서 제시되어 있듯이 바로 어제받은 떡의 갯수 + 그저꼐 받은 떡의 갯수가 셋 째날 받은 떡의 갯수가 된다.

즉, A[3] = A[1] + A[2] 가 될 것이고, B[3] = B[1] + B[2]가 될 것이다.

결과적으로 'D번째날'에 대한 떡의 갯수를 구하기 위해서 A와 B앞에 붙는 계수를 구하기 위해서는 다음과 같은 수식을 사용하면 될 것이다.

A[D] = A[D - 1] + A[D - 2]

B[D] = B[D - 1] + B[D - 2]

이를 점화식으로 우리는 첫 번째 날부터 D번째 날 까지의 A와 B의 계수를 모두 구할 수 있다.

#2. 정답 도출하기

위에서 계수를 모두 구해놨으면 이제부터는 정답을 도출해보자.

문제에 나온 예시를 한번 가져와 보겠다. D = 6 이고 K = 41인 경우이다.

즉, 여섯번째 날 호랑이에게 준 떡의 갯수가 41개일 때, 첫 째날과 둘 째날에 호랑이에게 준 떡의 갯수를 구하여라 라는 것이다.

우리는 #1에서 A와 B를 통해서 식을 나타냈으니 이 식을 한번 가져와보자.

#1을 통해서 우리는 여섯번째 날에는 호랑이에게 3A + 5B 개의 떡을 줘야 한다는 것을 알고 있다.

그럼 3A + 5B = 41 이 되어야 한다는 것인데, 이제부터 이를 구해볼 것이다. 어떻게 구할까 ??

바로 'A'에 1부터 K까지 순차적으로 값을 하나씩 넣어보면서 모두 탐색해 보는 것이다.

그럼 A에 1을 넣었다고 가정해보자. 즉, 첫 째날 호랑이에게 준 떡의 갯수가 '1개' 라고 가정해보는 것이다.

그럼, 3 + 5B = 41 이 되어야 하는데, 이를 만족하는 B가 있을까 ??? 문제에는 A와 B는 항상 정수라고 했기 때문에 만족하는 B가 없을 것이다. 너무나도 간단한 식이기에 우리는 눈으로 보자마자 3 + 5B = 41 을 만족시키는 B는 없다 라고 말을 할 수 있지만 이를 코드로 표현을 해주어야 한다.

위의 식에서 만족하는 정수 B가 있고 없고는 모듈러 연산을 통해서 간단하게 구할 수가 있다.

3 + 5B = 41에서 이 식을 정리하면 5B = 38 이라는 식이 되고, 38 % 5가 0이냐 아니냐를 통해서 이 식을 만족하는 정수 B가 존재하는지 안하는지를 판단할 수 있다.

즉, 코드로 나타내면 다음과 같다.

for (int i = 1; i <= K; i++)
{
    int Spare = K - (A[D] * i);
    if (Spare % B[D] == 0)
    {
        cout << i << endl << Spare / B[D] << endl;
        return;
    }
}

line1)에 있는 for문은 'A'값에 1부터 순차적으로 값을 넣어주기 위한 값이다.

line4)에서 보면, A를 계산하고 남은 떡의 양과 B의 계수와의 모듈러 연산을 통해서 식을 만족하는 정수가 있는지 없는지를

찾는 과정이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 35
using namespace std;
 
int D, K;
int A[MAX];
int B[MAX];
 
void Input()
{
    cin >> D >> K;
}
 
void Solution()
{
    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 = 1; i <= K; i++)
    {
        int Spare = K - (A[D] * i);
        if (Spare % B[D] == 0)
        {
            cout << i << endl << Spare / B[D] << endl;
            return;
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}