백준 1351

백준 1351 : 무한 수열

1. DP라고 문제에 써있다.
2. 단지 숫자가 커서 캐시를 배열로 쓰긴 힘들다
3. 따라서 map을 이용해서 memoization을 해야 한다.

정답 코드

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int n, p, q;
map<long long, long long> cache;

long long dp(long long k) {
	if(cache[k]) {
		return cache[k];
	}
	
	cache[k] = dp(k/p) + dp(k/q);
	return cache[k];
}

int main() {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n>>p>>q;
	
	cache[0] = 1;
	long long ans = dp(n);
	
	cout<<ans<<'\n';
	

	return 0;
}

왜 division by zero 오류가 뜰까

-> n, p, q를 int 형으로 선언해버림.. long long으로 바꾸니까 바로 맞았다.