백준 1351번: 무한 수열 (C++)

https://www.acmicpc.net/problem/1351

1351번: 무한 수열

---

Solved By: DP, Map

 

문제에서는 점화식이 주어졌으나 N의 범위가 너무 커서 배열로 다루기엔 불가능합니다.

그래서 map을 사용하여 Top-Down DP를 돌려주었습니다.

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

typedef long long ll;

ll N, P, Q;
map<ll, ll> m;

ll solve(ll n){
    if(n == 0) return 1; // base case
    
    if(m[n] != 0) return m[n];
    return m[n] = solve(n / P) + solve(n / Q);
}

int main(){
    cin >> N >> P >> Q;
    cout << solve(N);
    return 0;
}