[2502] 떡 먹는 호랑이

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

2502번: 떡 먹는 호랑이

<문제>

점화식의 정의에 맞춰서, 1번째 초기값과 2번째 초기값이 몇개씩 들어갔는지를 파악한다.

모든 (a,b)의 조합을 뽑으려면 O(K^2), K=10만이지만

a를 먼저 k에서 제하고 남은것이 b로도 나누어 떨어진다면 가능한 (a,b)이므로

O(K)만에 답을 찾을 수 있다.

 

다만 이 문제는 2중 for로 돌려도 조기에 break가 발생하여 TLE가 안나오는 것 같다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v;
int d, k;
int main(void) {
    cin >> d >> k;
    v.resize(d + 1);
    v[0] = {0, 0};
    v[1] = {1, 0};
    v[2] = {0, 1};
    for (int i = 3; i <= d; i++)
        v[i] = {v[i - 2].first + v[i - 1].first,
                v[i - 2].second + v[i - 1].second};
    for (int a = 1; a <= k; a++) {
        int x = k - v[d].first * a;
        if (x % v[d].second == 0) {
            cout << a << '\n' << x / v[d].second;
            break;
        }
    }
    return 0;
}