[백준] 자바 문제 풀이 1351 : 골드5

BOJ 1351 : 무한 수열

import java.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main {
    static HashMap<Long, Long> hm = new HashMap<>();
    public static long dp(long n, long p, long q) {
        if(hm.containsKey(n)) return  hm.get(n);
        hm.put(n, dp((long)Math.floor((double) n/p), p, q) + dp((long)Math.floor((double) n/q), p, q));
        return hm.get(n);
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer str = new StringTokenizer(br.readLine());

        long n = Long.parseLong(str.nextToken());
        long p = Long.parseLong(str.nextToken());
        long q = Long.parseLong(str.nextToken());

        hm.put(0L, 1L);
        bw.write(dp(n, p, q) + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}