#1354 무한 수열 2(Dynamic Programming)

이번 문제는 #1351과 같은 문제이지만, 숫자 범위가 좀 더 커지고, 두개의 숫자 인덱스를 계산하는 것이 좀 다릅니다.  그러다 보니 제한시간이 2초에서 10초로 대폭 늘었습니다.  난이도도 Gold IV에서 Gold III로 조금 높게 평가되었습니다.

 

그렇지만 똑같이 동적 프로그래밍을 이용하고 있고, 동적 프로그래밍상 히트율이 많이 낮아져서 시간이 많이 걸립니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

 

//----------------------------------------------------------
//  baekjoon #1354 - Infinity Series 2
//    - by Aubrey Choi
//    - created at 2020-02-02
//----------------------------------------------------------
#include <stdio.h>
#include <unordered_map>

std::unordered_map<long long, long long> dp;
long long p, q, x, y;
long long get(long long n)
{
  if(n<=0) return 1;
  if(dp[n]) return dp[n];
  return dp[n]=get(n/p-x)+get(n/q-y);
}
int main()
{
  long long n;
  scanf("%lld%lld%lld%lld%lld",&n,&p,&q,&x,&y);
  printf("%lld\n", get(n));
}