백준 1351 - 무한 수열

noj.am/1351

 

P, Q가 최소 2이기에 N을 계속 쪼개는 과정은 지수적 감쇠를 생각하면 그렇게 많은 연산을 요하지 않음을 알 수 있다.

 

따라서 동적계획법을 통해 쪼개가면서 얻은 값을 저장하면 빠르게 풀 수 있을텐데 문제는 N의 범위가 커서 배열로 저장을 할 수 없다는 것이다.

 

이를 해결하기 위해 map을 사용하여 값을 저장하면 필요한 값만 메모리를 사용하기 때문에 메모리 할당에 문제 없이 문제를 풀 수 있다.

 

전체 코드

#include <iostream>
#include <unordered_map>
 
using namespace std;
using ll = long long;
 
unordered_map<ll, ll> dp;
ll n, p, q;
 
ll memo(ll num)
{
    if (dp.count(num))
        return dp[num];
    return dp[num] = memo(num / p) + memo(num / q);
}
 
int main()
{
    dp[0] = 1;
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n >> p >> q;
 
    cout << memo(n);
}