[백준] 1351번

💻 C++ 기반

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

✔️ bottom-up DP를 이용하면 N이 너무 커서 안됨
✔️ top-down 방식을 사용할건데 그냥 재귀를 사용하면 시간초과가 남 -> 값을 저장해주는 메모이제이션 필요

#include <cstdio>
#include <unordered_map>

using namespace std;

long long N, P, Q;
unordered_map<long long, long long> m;

long long dp(long long num)
{
    if (m.find(num) != m.end())
    {
        return m[num];
    }
    else
    {
        return m[num] = dp(num/P) + dp(num/Q);
    }
}

int main()
{
    scanf("%lld %lld %lld", &N, &P, &Q);
    m[0] = 1;
    printf("%lld", dp(N));

    return 0;
}