#1351 무한 수열 (Dynamic Programming)

이번 문제는 Gold IV 난이도로 설정되어 있습니다.

 

무한히 이어지는 수열이 있는데, 이 수열은 다음과 같은 규칙을 가지고 있습니다.

주어진 자연수 P, Q에 대하여 \(A_i\) 항은,

 

\[ A_i = A_{ \lfloor i/P \rfloor } + A_{\lfloor i/Q \rfloor } \]

 

계속 나누어주는 것이기 때문에 \(A_0\)까지 가는데 빠릅니다.  많아야 \( \log_{P} N + \log_{Q} N \) 번이니까요.  동적 프로그래밍을 이용해서 풀어놓기는 했지만, 그냥 풀어도 적절한 시간안에 풀 수 있는 문제일거라고 보입니다.  N의 숫자가 크기 때문에 저는 map 자료구조를 이용해서 풀었습니다.  풀어놓고 보면, 정말 쉬운 문제입니다.  소스도 크게 어려울 것이 없습니다.

 

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

//----------------------------------------------------------
//  baekjoon #1351 - Infinity Series
//    - by Aubrey Choi
//    - created at 2020-01-16
//----------------------------------------------------------
#include <stdio.h>
#include <unordered_map>

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