백준 1351 무한수열

백준 1351

10^12 이기 때문에 배열로는 메모이제이션 하기에는 불가능
=> map을 이용

처음에 bottom-up 방식으로 풀려고 했지만 메모리 초과가 났다
top-bottom 방식으로 바꿔서 풀었다. 아마 bottom-up 방식은 mp[1]부터 mp[n]까지 모든 mp를 구해야 하는 반면, top-bottom 방식에서는 n에서부터 내려오는데 mp[n/p],mp[n/q]로 필요한 것만 계속해서 계산하기 때문에 메모리 초과가 안나는 것 같다.

#include <bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
long long n;
int p, q;
unordered_map<long long, long long>mp;
long long dfs(long long n) {

	if (n == 0) return 1;

	if (mp[n]) return mp[n];
    
	return mp[n]=dfs(n / p) + dfs(n / q);

}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> p >> q;

	mp[0] = 1;

	cout << dfs(n) << '\n';

}