[BOJ] 무한 수열 2 - Compy's Blog

TimeLimit	MemoryLimit	Condition	TAG
10s	128MB	(1 <= N <= 10¹³, 2<= P, Q <= 10⁹,0<= X, Y <= 10⁹)	Dynamic Programming(DP)

$\begin{array}{l} A_{i} = 1 (i \leq 0) \\ A_{i} = A_{⌊ \frac{i}{P} ⌋ - X} + A_{⌊ \frac{i}{Q} ⌋ - Y} (i \geq 1) \end{array}$
N, P, Q, X, Y가 주어질 때, AN을 구하는 프로그램을 작성하시오.

이건 1번에서 뭐 사실 똑같이 풀면 됩니다. 10초라서 디게 쉽게 접근할 수 있었고, 그냥 0이하일 때 1을 반환 하도록 하면 됩니다.

정답 코드

#include <iostream>
#include <map>

using namespace std;

using ll = long long;
map<ll, ll> dp;
ll N, Q, P, X, Y;
ll solution(ll n){
    if(dp.find(n) != dp.end()) return dp[n];
    if(n <= 0) return 1LL;
    ll result = solution((ll)(n/Q)-X) + solution((ll)(n/P)-Y);
    dp.insert({n, result});
    return result;
}

int main(){
    dp.insert({0, 1});
    cin >> N >> Q >> P >> X >> Y;
    
    cout << solution(N);
    
    return 0;
}