[백준] 1351번 무한 수열

[적용한 알고리즘]

DP

 

[아이디어]

N 이 어마어마하게 큰데, 필요한 배열의 개수는 

log2 10^12 이기 때문에 그리 많지 않다. 

따라서 map 을 이용하면 될 것이다. 

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

내용

 

<코드>

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef long long lld;

map<lld, lld> dp;
lld N, P, Q;

lld go(lld i){
    if (i == 0) return 1;
    if (dp[i] > 0) return dp[i];
    return dp[i] = go(i / P) + go(i / Q);
}

int main(){
    scanf("%lld %lld %lld", &N, &P, &Q);
    printf("%lld", go(N));
    return 0;
}