boj 1354 무한 수열 2

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

 

• Ai = 1 (i ≤ 0)
• Ai = A⌊i / P⌋ - X + A⌊i / Q⌋ - Y (i ≥ 1)

여기에서 An을 구하는 문제입니다.

우선 N이 10^13이기 때문에 단순 배열만으로는 해결할 수 없습니다.

그래서 처음 생각해낸건 map을 사용하여 dp를 해결하려고 했습니다.

 

dp 재귀를 돌릴 때 dp[n] != -1이면 dp[n]을 리턴했던것 처럼

map에 포함되어 있는 수는 이미 방문처리가 되었으므로 그 수를 리턴하도록 합니다.

 

 

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
 
unordered_map<ll, ll> m;
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n <= 0) return 1LL;
    if (m.find(n) != m.end()) return m[n];
    return m[n] = solve(n / p - x) + solve(n / q - y);
}
 
void func() {
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

 

근데 생각보다 메모리를 많이 차지하고, 시간도 많이 소요되는 것을 알 수 있습니다.

다른분들의 제출 현황을 보니 이 방법은 비효율적이라는 것을 알 수 있었습니다.

 

제가 확인해봤던 풀이로는 배열을 활용하는 방법이었습니다.

하지만 N의 범위가 10^13이기 때문에 모든 범위를 배열로 해결할 수는 없습니다.

문제에서 허용하는 메모리 512MB 내에서는 가능하기 때문에 10000000 까지는 배열로, 나머지는 재귀로 해결할 수 있었습니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 10000001
using namespace std;
typedef long long ll;
 
ll dp[MAX];
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n < MAX) return dp[n];
 
    ll l = 1LL;
    if (n / p - x > 0) l = solve(n / p - x);
 
    ll r = 1LL;
    if (n / q - y > 0) r = solve(n / q - y);
 
    return l + r;
}
 
void init() {
    dp[0] = 1LL;
    for (int i = 1; i < MAX; i++) {
        dp[i] = dp[max(0LL, i / p - x)] + dp[max(0LL, i / q - y)];
    }
}
 
void func() {
    init();
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

 

아까와 비교하면 메모리와 시간 차이가 정말 많이 난다는 것을 알 수 있습니다.