[C++/백준] 2502번: 떡 먹는 호랑이

문제 링크

2502번: 떡 먹는 호랑이

 

풀이

1. 먼저 첫째날에 x개, 둘째날에 y개 줬다고 했을 때 d째 날에 x와 y를 이용한 연립방정식을 구한다.
   1. 이건 DP로 풀면 된다. x와 y는 따로 계산 될 것이니 각 {0, 1, 0, }, {0, 0, 1, }로 초기화해서 전전날과 전날의 합을 구하면 된다.
   2. 예를 들어, 여섯 번째 날에 x와 y의 연립방정식을 구하고 싶다면, x[6]에 있는 3, y[6]에 있는 5를 이용해 3x+5y라는 식을 만들 수 있다.
2. 식을 구했으니 이젠 완전 탐색을 이용해 x와 y를 구하면 된다. 단, 여기서 y는 x보다 크거나 같아야 하므로 내부의 반복문은 i부터 시작하도록 한다.
3. x[d]*i+y[d]*j가 k와 같다면 출력하고 return한다.

 

코드

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int d, k;
    cin >> d >> k;

    // 첫째날에 x개, 둘째날에 y개 줬다 했을 때
    // d번째 날에 x와 y의 연립방정식
    int x[31] = { 0,1,0, };
    int y[31] = { 0,0,1, };
    for (int i = 3; i <= d; i++)
    {
        x[i] = x[i - 2] + x[i - 1];
        y[i] = y[i - 2] + y[i - 1];
    }

    for (int i = 1; i <= k; i++)
    {
        for (int j = i; j <= k; j++)
        {
            if (k == x[d] * i + y[d] * j)
            {
                cout << i << '\n' << j;
                return 0;
            }
        }
    }
}