[Algorithm] BOJ 1351 무한 수열

문제 링크

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

문제 풀이

문제에서 제공한 점화식을 이용해 재귀함수를 작성해서 풀면 되는 문제이다.
메모이제이션을 이용한 DP로 문제를 풀 경우, N의 범위가 $10^{12}$ 이므로, 배열로는 안되고 map 을 이용해서 풀어야한다 !

코드

#include <iostream>
#include <map>

using namespace std;

long long P, Q;
map<long long, long long> cache;

long long solve(long long n) {
    if (n == 0) return 1;

    if (cache[n] != 0) return cache[n];
    return cache[n] = solve(n/P) + solve(n/Q);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    long long n;
    cin >> n >> P >> Q;
    cout << solve(n);


    return 0;
}