백준 1354번, 무한 수열 2 풀이

문제

백준 1354번

풀이

문제는 $ A_{n} $을 구하는 것입니다.

$ A_{i} $에 대한 점화식이 문제에 나와 있으니 재귀적으로 풀어봅시다.

 

피보나치 수열과 마찬가지로 비슷한 값의 중복 연산을 피하기 위해 DP를 사용해야 합니다.

이 문제의 경우 항 $ i $가 불연속적이고 매우 크므로, map을 사용해야 메모리 초과를 피할 수 있습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

unordered_map<ll, ull> mp;
ll n, p, q, x, y;

ull solve(ll i) {
	if (i <= 0) return 1;
	if (mp[i]) return mp[i];
	return mp[i] = solve(i / p - x) + solve(i / q - y);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> p >> q >> x >> y;

	cout << solve(n);
}