(1351) 무한 수열

문제

무한 수열 A는 다음과 같다.

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

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력

첫째 줄에 AN을 출력한다.

제한

• 0 ≤ N ≤ 1012
• 2 ≤ P, Q ≤ 109

---

문제 풀이

해당 문제는 DP 알고리즘으로 해결 할 수 있는 문제입니다. 

 

초기에는 타뷸레이션으로 접근하였으나, 시간초과 문제로 메모이제이션 방식으로 처리 했습니다.

 

메모이제이션은 이미 계산된 값을 저장해 두고 필요할 때 재사용하는 방식입니다. 이전에 계산한 값을 메모리에 저장해 두는 캐시(cache)를 이용하여 중복 계산을 피하는 방식입니다. 메모이제이션은 재귀 함수를 사용하여 구현하는 경우가 많으며, 재귀 함수 호출이 많은 경우 중복 계산이 많이 발생할 수 있기 때문에 이를 줄이는데 유용합니다.

 

타뷸레이션은 작은 문제부터 차례대로 해결해 나가는 방식입니다. 이전에 계산한 값을 저장하지 않고, 작은 문제부터 순서대로 해결하여 큰 문제를 해결하는 방식입니다. 이 방식은 일반적으로 반복문을 사용하여 구현합니다.

---

나의 답안

import java.io.*;
import java.util.*;

public class Main {

    static Map<Long, Long> map = new HashMap<>();
    static long P, Q;

    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());


        long result = solve(N);

        System.out.println(result);
    }

    private static long solve(long n) {
        if (n == 0) return 1;
        if (map.containsKey(n)) return map.get(n);

        map.put(n, solve(n / P) + solve(n / Q));

        return map.get(n);
    }

}