[BOJ] 1354_무한 수열 2

무한 수열 2

링크: https://www.acmicpc.net/problem/1354

1354번: 무한 수열 2

 

n을 기준으로 하여 dp 배열을 생성하게 되면, 10^13의 크기를 생성할 수 없다.
따라서, 배열로 dp문제를 해결할 수 없다.

 

map을 통해 필요한 index만 저장하고 꺼내서 사용하는 방식을 사용한다.

 

• 정답 코드

    #include<iostream>
    #include<unordered_map>
    using namespace std;
    long long n, p, q, x, y;
    unordered_map<long long, long long> dp;
    long long An(long long i) {
        if (i <= 0)
            return 1;
  
        auto iter = dp.find(i);
        if (iter != dp.end())
            return iter->second;
  
        long long int a = An(i / p - x), b = An(i / q - y);
        dp[i] = a + b;
  
        return a + b;
    }
  
    int main() {
        cin >> n >> p >> q >> x >> y;
        cout << An(n);
        return 0;
    }