백준 1351 자바 - 무한 수열

// 무한 수열
package Gold_V_5;

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 Ex1351 {

    static long n;
    static int p;
    static int q;
    static Map<Long, Long> map = new HashMap<>();

    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 = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());

        System.out.println(get(n));
    }

    static long get(long key) {
        if (map.get(key) == null) { put(key); }
        return map.get(key);
    }

    static void put(long key) {
        if (key == 0L) {
            map.put(0L, 1L);
        } else {
            map.put(key, get(key / p) + get(key / q));
        }
    }
}

원래는 아래 코드처럼 작성했었지만 시간초과가 나서 위처럼 수정했다.

 

시간초과 난 코드

static void infinite(long n) {
        if (n == 0) {
            map.put(n, 1L);
        } else {
            infinite(n / p);
            infinite(n / q);
            map.put(n, map.get(n / p) + map.get(n / q));
        }
    }