[TopCoder] InfiniteSequence2(무한 수열)

다음과 같이 정의된 무한 수열 A를 생각해 보자:

Ai = 모든 i에 대해 1 <= 0;
Ai = 모든 i > = 1에 대해 Ai p A[i/p]-x + A[i/q]-y, 여기서 [x]는 x의 바닥 함수를 나타낸다(참고 참조)
n, p, q, x, y가 주어집니다. A의 n번째 요소(인덱스는 0 기반)를 반환합니다.

Definition

Class:

 

InfiniteSequence2

Method:

 

calc

Parameters:

 

long long, int, int, int, int

Returns:

 

long long

Method signature:

 

long long calc(long long n, int p, int q, int x, int y)

(be sure your method is public)

Examples

0)

10000000

2

3

10000000

10000000

Returns: 2

A[10000000] = A[-5000000] + A[-6666667] = 2.

1)

12

2

3

1

0

Returns: 8

 

2)

0

2

2

0

0

Returns: 1

A[0] = 1.

 

3)

123

45

67

8

9

Returns: 2

---

간단해 보이는 문제이지만, 시공간 복잡도 제약으로 인해서 고민해야할 부분이 많은 문제이다. 

 

메모화 재귀를 하려니, 공간 복잡도가 너무 커지고 단순 재귀를 하자니 시간 복잡도가 너무 커진다. 

 

해결책은 자주 발생하는 부분은 메모화 재귀로 풀고, 자주 발생하지 않는 부분은 단순 재귀로 푸는 것이다. 

 

#include <vector>
#include <cmath>
using namespace std;

class InfiniteSequence2{
    public:
    const int MAX = 1e6;
    long long dp[1000000];
    long long calc(long long n, int p, int q, int x, int y){
        return recursion(n, p, q, x, y);
    }

자주 발생하는 부분은 작은 수들이다. 파라미터로 들어오는 n이 100만보다 작을 경우에는 메모화 재귀로 해결하고

 

그 이상일 경우에는 단순 재귀로 풀어나간다. 메모화를 위한 배열 dp도 넉넉한 크기고 선언하였다. 

 

    long long recursion(long long i, int p, int q, int x, int y){
        if(i<=0){
            return 1;
        }

재귀 함수 부분이다. 들어오는 i가 0이하일 경우 1을 반환한다. 

 

        long long nexta = floor(i/p) - x;
        long long nextb = floor(i/q) - y;

i번째 수를 계산하기 위한 next i를 계산해준다. 

        if(i<MAX){
            if(dp[i]!=0){
                return dp[i];
            }
            else{
                return dp[i] = recursion(nexta, p, q, x, y) + recursion(nextb, p, q, x, y);
            }
        }

i가 자주 발생하는 작은 수일 경우 메모화 재귀로 해결한다. 

        else {
            return recursion(nexta, p, q, x, y) + recursion(nextb, p, q, x, y);
        }

큰 수일 경우에는 메모하지 않고, 일반 재귀로 해결한다.