1351: 무한 수열

[minsoo0715]

1351 : 무한 수열

소스 코드

아이디어

메모이제이션 문제로 보인다.
대신 수열의 형태가 아래와 같으므로 $N$이 급격하게 줄어드는 경향이 있어 저장할 $A_i$가 띄엄띄엄 존재할 뿐만 아니라, 값의 범위가 long을 초과하기 때문에 배열로 저장하기에는 무리가 있다.
$A_i = A_{i/P} + A_{i/Q} (i ≥ 1)$

따라서 Key-Value로 저장하는 자료구조, map을 사용하면 될 것으로 보인다.

구현

std::vector대신 std::map을 통해 메모이제이션, 재귀 함수를 사용해 top-down 방식으로 구현

#include <iostream>
#include <map>

using ll = long long int;

std::map<ll, ll> dp;
ll p, q;

ll solve(ll n) {
    if(n == 0) {
        return 1;
    }
    if(dp[n] != 0) {
        return dp[n];
    }
    return dp[n] = solve(n/p) + solve(n/q);
}