[BOJ] 무한 수열 1 - Compy's Blog

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 <= N <= 10¹², 2<= P, Q <= 10⁹)	Dynamic Programming(DP)

$\begin{array}{l} A_{0} = 1 \\ A_{i} = A_{⌊ \frac{i}{P} ⌋} + A_{⌊ \frac{i}{Q} ⌋} (i \geq 1) \end{array}$
N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

이것은 깊게 생각할 필요없이 그냥 map을 이용해서 풀이했습니다. 그런데 2차원 dp로도 풀 수 있겠더라구요.

효율적으로 풀이하려면 map보다는 array를 사용하는게 맞는 것 같습니다.

정답 코드

#include <iostream>
#include <map>
using namespace std;

using ll = long long;
map<ll, ll> dp;
ll N, Q, P;
ll solution(ll n){
    if(dp.find(n) != dp.end()) return dp[n];
    
    ll result = solution((ll)(n/Q)) + solution((ll)(n/P));
    dp.insert({n, result});
    return result;
}

int main(){
    dp.insert({0, 1});
    cin >> N >> Q >> P;
    
    cout << solution(N);
    
    return 0;
}