백준 1351번: 무한 수열

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

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

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

처음에는 단순하게 백트래킹만으로 풀이하였다. 현재 n을 current/p 번째 항, current/q 번째 항으로 나누어 구한 후 더한 값을 반환하게 하였다.

private static long backtracking(long current) {
    if (current == 0) {
        return 1;
    }
    return backtracking(current / p) + backtracking(current / q);
}

 

 

그러나 current/p, current/q 가 같은 값을 가지게 되는 경우가 많아 많은 횟수를 반복하게 되고 시간 초과가 발생하였다. 그러므로 current/p, current/q가 이미 방문한 값을 재방문하지 않게 하기 위해 Map<Long, Long>을 이용하여 재방문 시 저장한 값을 반환하게 하여 해결하였다.

static Map<Long, Long> memo = new HashMap<>();

private static long backtracking(long current) {
    if (current == 0) {
        return 1;
    }
    if (memo.get(current) != null) {
        return memo.get(current);
    }
    
    long result = backtracking(current / p) + backtracking(current / q);
    memo.put(current, result);
    return result;
}

 

 

결과 코드는 다음과 같다.

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