백준 2502 떡 먹는 호랑이

백준 2502 떡 먹는 호랑이

---

오늘은 떡먹는 호랑이라는 문제를 풀어보았다.


사실 이 문제는 그냥 머리 굴려서 풀어보라고 하면 되게 쉬운 문제이다.

첫 날 준 떡을 a개, 둘째날 준 떡을 b개라고 했을 때 그 a,b 가 n번째 되는날 몇개씩 있는지 확인해 값을 대입해 찾기만 하면 되는데, 이 a,b 값이 뭔지 모르는 상태에서 더해가며 가져가는것 구현을 잘 생각을 해야 한다.

난 그래서 크기2 짜리 벡터를 만들어 a 와 b 의 개수를 저장하는 dp 를 만들었다. 그 후, i 를 1부터 i*a의 개수 값이 k 보다 작을 때까지 순회하며 만족하는 a,b 값을 찾으면 바로 리턴하도록 했다!

 for (int i = 3; i <=d ;i++)
    {
        dp[i][0] = dp[i-1][0] + dp[i-2][0];
        dp[i][1] = dp[i-1][1] + dp[i-2][1];
    }

아이디어가 어렵지 않아서 풀 수 있던 것 같다. 사실 dp인지도 잘 모르겠음ㅎ

#include <iostream>
#include <vector>

using namespace std;

long long dp[33][2];
int main()
{

    int d, k;

    cin>>d>>k;
    dp[1][0] = 1;   //각각 a, b 의 개수 의미
    dp[1][1] = 0;
    dp[2][0] = 0;
    dp[2][1] = 1;

    for (int i = 3; i <=d ;i++)
    {
        dp[i][0] = dp[i-1][0] + dp[i-2][0];
        dp[i][1] = dp[i-1][1] + dp[i-2][1];
    }

    //cout << dp[d][0] << " " << dp[d][1] << "\n";

    for (int i = 1; i * dp[d][0] < k; i++ )
    {
        if (  (k - (i*dp[d][0]))%dp[d][1] == 0 )
        {
            cout<< i << "\n";
            cout<<(k - (i*dp[d][0]))/dp[d][1] <<"\n";
            return 0;
        }
    }
    return 0;
}