[백준 1351] 무한 수열 (C++)

이 문제는 점화식이 주어진 dp문제이다.

얼핏보면 실버처럼 쉬워보이지만, 제한조건때문에 난이도가 올라가는 문제이다.

${N} \le {10^{12}}$이므로 bottom-up방식의 dp로는 시간 초과가 난다.
top-down을 하자니 중복 연산이 생기므로 최적화를 위해, 메모제이션을 해주도록 하자.

하지만, 모든 값을 메모제이션 한다면, $N$이 최대 $10^{12}$이므로 수백GB의 메모리가 필요하게 된다.

따라서, 필요한 값만 메모제이션을 해야하므로 unordered_map을 이용해야 한다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, p, q;
unordered_map<ll, ll> um;

ll solve(ll x) {
	if (x == 0) return 1;
	if (um.find(x / p) == um.end()) um[x / p] = solve(x / p);
	if (um.find(x / q) == um.end()) um[x / q] = solve(x / q);
	return um[x / p] + um[x / q];
}

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

	cin >> n >> p >> q;
	cout << solve(n);
}