BOJ - 무한 수열2(C++)

문제 출처: https://www.acmicpc.net/problem/1354

문제 난이도

Gold 3

문제 접근법

문제에 점화식이 다 나와있기 때문에 접근하기는 쉽다.
하지만 N이 10000000000000까지 있는데 이걸 충족할 DP를 선언하지 못했다.
결국 찾아보니 Map으로 사용한 걸 봤고, DP를 굳이 배열로만 선언할 필요가 없다는 걸 새삼 깨달았다.

주의
모든 변수형은 long long으로 할 것!!

통과 코드

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstdio>

using namespace std;

unordered_map<long long, long long> A;
long long N, P, Q, X, Y;

long long dfs(long long i) {
	if (i <= 0) return 1;
	if (A[i]) return A[i];
	return A[i] = dfs(i / P - X) + dfs(i / Q - Y);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> P >> Q >> X >> Y;
	cout << dfs(N) << "\n";
	return 0;
}

피드백

제한 시간이 10초 이내에다가 통과까지 진짜 오래걸린다