[백준 1354번] [Unordered_map / DP] 무한 수열 2

Approach

근본적으로 다음 문제와 접근 방법은 완전하게 동일하다.

https://viyoung.tistory.com/277

[백준 1351번] [Map / DP] 무한 수열

다만, 데이터의 양이 매우 많은 상황이고 순서가 크게 중요하지 않은 상황이므로 해시를 활용한 맵인 Unordered_map을 활용하여 시간을 줄여주면 통과하는 문제이다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;
unordered_map<ll, ll> s;
ll n, p, q, x, y;

ll s_value(ll v){
    if(v <= 0) return 1;
    if(s[v]) return s[v];
    else return s[v] = s_value(v / p - x) + s_value(v / q - y);
}

int main(void){
    fastio;
    cin >> n >> p >> q >> x >> y;
    cout << s_value(n) << "\n";
    return 0;
}