백준 1354번: 무한 수열 2

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

 

주어진 n, p, q, x, y이 주어질 때 다음의 조건을 만족하는 수열에 대해서 An을 구하는 문제이다. 0 <= n <= 10^13, 2 <=p,q <= 10^9, 0 <= x, y <= 10^9, 제한시간은 10초이다.

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

1351번 무한 수열과 동일하게 방문한 값을 재방문하지 않게 하기 위해 Map<Long, Long>을 이용하여 재방문 시 저장한 값을 반환하는 백트래킹으로 풀이하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class 무한수열1354 {
    
    private static Map<Long, Long> map = new HashMap<>();
    private static long n, p, q, x, y;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Long.parseLong(st.nextToken());
        p = Long.parseLong(st.nextToken());
        q = Long.parseLong(st.nextToken());
        x = Long.parseLong(st.nextToken());
        y = Long.parseLong(st.nextToken());
        
        System.out.print(backtracking(n));
    }
    
    private static long backtracking(long current) {
        if (current <= 0) {
            return 1;
        }
        if (map.get(current) != null) {
            return map.get(current);
        }
        
        long result = backtracking(current / p - x) + backtracking(current / q - y);
        map.put(current, result);
        return result;
    }
}

 

 

위의 방식대로 796176 kb의 메모리와 4836ms가 소요되었다. 이를 더 최적화하기 위해 자주 호출되는 작은 값들은 더 빠른 배열에 저장하고 큰 값들만 Map에 저장하여 시간과 메모리를 모두 단축할 수 있다. 메모리 제한에 맞추어 10000000의 long[] 을 선언하고 100000000 이상의 값은 Map에 저장하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class 무한수열1354 {
    
    private static final int MAX_CACHE = 10000000;
    private static long[] arrayCache = new long[MAX_CACHE];
    private static Map<Long, Long> mapCache = new HashMap<>();
    
    private static long n, p, q, x, y;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Long.parseLong(st.nextToken());
        p = Long.parseLong(st.nextToken());
        q = Long.parseLong(st.nextToken());
        x = Long.parseLong(st.nextToken());
        y = Long.parseLong(st.nextToken());
        
        System.out.print(solve(n));
    }
    
    private static long solve(long current) {
        if (current <= 0) {
            return 1;
        }
        
        if (current < MAX_CACHE) {
            if (arrayCache[(int) current] != 0) {
                return arrayCache[(int) current];
            }
        } else {
            if (mapCache.containsKey(current)) {
                return mapCache.get(current);
            }
        }
        
        long result = solve(current / p - x) + solve(current / q - y);
        
        if (current < MAX_CACHE) {
            arrayCache[(int) current] = result;
        } else {
            mapCache.put(current, result);
        }
        
        return result;
    }
}

 

 

230984kb의 메모리와 1452ms가 소요되어 상당한 향상 효과를 얻었다.