[BOJ] 1351번 : 무한 수열 C++ 풀이

간단한 탑다운 DP 문제이다.
Ai = A[i/P] + A[i/Q]일때, An을 구해야 한다. N이 최대 1e12까지 가능하다.

P와 Q는 최소 2부터 시작이다. 따라서 트리 구조로 탐색을 진행한다고 생각해봤을때, 트리의 깊이가 급격히 낮아지는 것을 알 수 있다. 중복되지 않는다고 해도 최대 log2 1e12안에 모든 탐색을 할 수 있다. 이는 깊이 38짜리 트리이다.

방문을 표시하기 위한 배열을 만들 수 없으니, map을 활용하기로 하자. 이제 배열대신 map에 값을 사용해서 재귀 탐색을 수행할 수 있다.이미 구했던 값을 다시 계산할 필요가 없으므로 메모이제이션 기법을 함께 활용하면 아주 간단히 풀린다. 

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 100010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
ll N, P, Q;
map<ll, ll> mp;

ll dfs(ll curr) {
    if (mp[curr] != 0) return mp[curr];
    mp[curr] = dfs(curr/P) + dfs(curr/Q);
    return mp[curr];
}

void init() {
    cin >> N >> P >> Q;
    mp[0] = 1;
    cout << dfs(N) << '\n';
} 

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}