1351 무한 수열

#include <stdio.h>
#include <map>
 
using namespace std;
 
long long dfs(long long num);
 
long long p, q;
map<long long, long long> mp;
 
int main() {
    long long n;
    scanf("%lld %lld %lld", &n, &p, &q);
    
    long long rst = dfs(n);
    printf("%lld", rst);
}
 
long long dfs(long long num) {
    if (num == 0)
        return 1;
 
    long long l = num / p;
    long long r = num / q;
    
    long long lv, rv;
    if (mp.find(l) != mp.end())
        lv = mp.find(l)->second;
    else {
        lv = dfs(l);
        mp.insert(make_pair(l, lv));
    }
 
    if (mp.find(r) != mp.end())
        rv = mp.find(r)->second;
    else {
        rv = dfs(r);
        mp.insert(make_pair(r, rv));
    }
 
    return lv + rv;
}

배열의 크기가 너무 커서 메모이제이션을 할 수 없을때 -> map stl 을 활용하자